Subset sum

subset_sum.clj

(def sum-of-pos-elements (memoize (fn [xs] (apply + (filter #(>= % 0) xs)))))
(def sum-of-neg-elements (memoize (fn [xs] (apply + (filter #(< % 0) xs)))))

(defn subset-sum
  "Returns the indexes of elements in xs whose sum is s"
  ([xs s]
    (subset-sum xs (dec (count xs)) s))
  ([xs i s]
   "Returns the indexes of elements x0...xi (in xs) whose sum is s"
   (let [sol (subset-sum xs i s [])]
     (if (empty? sol) nil sol)))
  ([xs i s sol]
    (let [P (sum-of-pos-elements xs)
          N (sum-of-neg-elements xs)]
      (cond
        (or (< s N) (> s P)) sol
        (zero? i) (if (= (first xs) s) (conj sol 0) sol)
        :else
          (let [not-using-xi-s (fn [] (subset-sum xs (dec i) s sol))
                not-using-xi-s-minus-xi (fn [] (subset-sum xs (dec i) (- s (nth xs i)) sol))]
          (cond
            (= (nth xs i) s) (conj sol i)
            (not (empty? (not-using-xi-s))) (not-using-xi-s)
            (not (empty? (not-using-xi-s-minus-xi))) (conj (not-using-xi-s-minus-xi) i)
            :else []))))))

(def subset-sum (memoize subset-sum))

Why not:

(def sum-of-pos-elements (memoize (fn [xs] (apply + (filter pos? xs)))))

?

Sure, that's even better :) I have yet to fully realize there's a function for everything in Clojure :)