Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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.

(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}})
)
(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}}
(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))))
;; 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))
(defn subset-sums [s ^long n] (->> s seq combo/subsets (map set) (filter #(= (reduce + %) n)) set))
(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)))
(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
Copy link

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)))

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