Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# ericnormand/00 subset sums.md

Last active Apr 15, 2020

Subset sums

Write a function that takes a set of numbers and returns all subsets that sum to a given number. That's a mouthful. Here's an example.

```;; subsets that sum to 6
(subset-sums #{1 2 3 4 5} 6) ;=> #{ #{1 5} #{2 4} }
;; subsets that sum to 7
(subset-sums #{1 2 3 5 6 7} 7) ;=> #{ #{1 6} #{2 5} #{7} }
;; subsets that sum to 0
(subset-sums #{0 1 -1} 0) ;=> #{ #{} #{0} #{1 -1} #{0 1 -1} }```

Thanks to this site for the challenge idea.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (ns tst.demo.core (:use tupelo.core tupelo.test) (:require [clojure.math.combinatorics :as combo] [schema.core :as s] [tupelo.schema :as tsk])) (s/defn total :- s/Int [vals] (reduce + 0 (seq vals))) (s/defn subset-sums :- #{#{s/Any}} [vals :- #{s/Int} tgt :- s/Int] (let [subsets (mapv set ; convert from list of lists => vector of sets (combo/subsets (vec vals))) ; requires a vector input keepers (set ; result is a set of sets (keep-if #(= tgt (total %)) subsets))] keepers)) (dotest (is= 0 (total [])) ; verify total function works for empty seqs (is= 1 (total [1])) (is= 3 (total [1 2])) (is= 6 (total [1 2 3])) (is= (subset-sums #{1 4 3 2 5} 6) #{#{1 5} #{4 2} #{1 3 2}}) (is= (subset-sums #{7 1 6 3 2 5} 7) #{#{7} #{1 6} #{2 5}}) (is= (subset-sums #{0 1 -1} 0) #{#{0 1 -1} #{} #{1 -1} #{0}}) )
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn subset-sums [numbers sum] (letfn [(positives [coll] (filter #(not= 0 %) coll)) (add [coll num-1] (map (fn [num-2] (if (= sum (+ num-1 num-2)) [num-1 num-2] 0)) coll)) (expand [numbers] (map (fn [num-1] (into #{} (flatten (positives (add numbers num-1))))) numbers))] (filter #(not (empty? %)) (into #{} (expand numbers))))) ;; subsets that sum to 6 (subset-sums #{1 2 3 4 5} 6) ;=> #{#{3} #{1 5} #{4 2}} ;; subsets that sum to 7 (subset-sums #{1 2 3 5 6 7} 7) ;=> #{#{1 6} #{2 5}} ;; subsets that sum to 0 (subset-sums #{0 1 -1} 0) ;=> #{#{1 -1} #{0}}
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (ns subset-sum (:require [clojure.test :refer [deftest is]])) (defn subsets [s] (loop [[x & xs] s r #{#{}}] (if x (recur xs (concat r (map #(into #{} (cons x %)) r))) (drop-last r)))) (defn subset-sums [s target] (->> (subsets s) (filter #(= target (reduce + %))) (into #{}))) (deftest subset-sum-test (is (= #{#{1 5} #{2 4} #{1 2 3}} (subset-sums #{1 2 3 4 5} 6))) (is (= #{#{1 6} #{2 5} #{7}} (subset-sums #{1 2 3 5 6 7} 7))) (is (= #{#{} #{0} #{1 -1}} (subset-sums #{0 1 -1} 0))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;; non-tail recursive is too slow, even with memoization (defn subsets* [f s] (->> s (map #(f f (disj s %))) (reduce clojure.set/union #{s}))) (defn subsets [s] (subsets* (memoize subsets*) (set s))) ;; tail-recursive version is much faster (defn subsets [s] (loop [ret #{#{}} rem s] (if (empty? rem) ret (let [[f & rst] rem] (recur (into ret (map #(conj % f)) ret) rst))))) (defn subset-sums [s n] (->> s subsets (filter #(= n (reduce + 0 %))) set))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn subset-sums [s ^long n] (->> s seq combo/subsets (map set) (filter #(= (reduce + %) n)) set))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn powerset [s] (if (empty? s) #{#{}} (clojure.set/union (powerset (next s)) (map #(conj % (first s)) (powerset (next s)))))) (defn subset-sums [s n] (filter #(= n (reduce + %)) (powerset s)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (ns purelyfunctional-newsletters.issue-372 (:require [clojure.test :refer :all] [clojure.string :as str])) (defn subsets [cur-numbers other-numbers accept-fn] (loop [result (if (accept-fn cur-numbers) #{cur-numbers} #{}) x (first other-numbers) xs (rest other-numbers)] (if (nil? x) result (let [other-results (subsets (conj cur-numbers x) xs accept-fn)] (recur (into other-results result) (first xs) (rest xs)))))) (defn subset-sums [xs target-sum] (subsets #{} xs (fn [input-numbers] (and (seq input-numbers) (= target-sum (apply + input-numbers)))))) (deftest subset-sums-testing (testing "basics" (are [x y] (= y x) (subset-sums #{} 0) #{} (subset-sums #{0 1} 0) #{#{0}} (subset-sums #{0 1} 1) #{#{0 1} #{1}} (subset-sums #{0 1 2} 2) #{#{0 2} #{2}} (subset-sums #{-1 1 -2 2} 0) #{#{-1 1 -2 2} #{-1 1} #{-2 2}}) (testing "examples" (are [x y] (= y x) (subset-sums #{1 2 3 4 5} 6) #{#{1 5} #{4 2} #{1 3 2}} (subset-sums #{1 2 3 5 6 7} 7) #{#{7} #{1 6} #{2 5}} (subset-sums #{0 1 -1} 0) #{#{0 1 -1} #{1 -1} #{0}}))))

### miner commented Apr 15, 2020

Here's my variation on Eric Normand's solution. It gains performance by using seqs for the intermediate subsets and deferring the creation of sets until needed.

``````(defn subset-sums [nums sum]
(into #{}
(comp (filter #(zero? (reduce - sum %)))
(map set))
(reduce (fn [ss x] (into ss (map #(conj % x)) ss)) (list ()) nums)))
``````

to join this conversation on GitHub. Already have an account? Sign in to comment