-
-
Save orb/6054330 to your computer and use it in GitHub Desktop.
my take on this problem
http://siscia.github.io/2013/07/21/algorithm-problem-for-job
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 can-sum-to-zero | |
([nums] | |
(can-zero nums #{})) | |
([nums can-sum-to] | |
(when (seq nums) | |
(let [num (first nums)] | |
(if (can-sum-to (- num)) | |
true | |
(let [can-also-sum-to (map #(+ num %) can-sum-to)] | |
(recur (rest nums) | |
(clojure.set/union can-sum-to can-also-sum-to #{num})))))))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This approach is a breadth first search of all the possible sums you can reach starting from the beginning of the list. It has the advantage of being able to prune subsets that sum to the same value, but since it does need to keep all the sums it can require more memory