This is the classic Subset sum problem (http://en.wikipedia.org/wiki/Subset_sum_problem) and is an NP one.
I've implemented the pseudo-polynomial dynamic programming solution found on the above Wikipedia page: https://gist.github.com/3359504 It returns the indexes of the elements that give the desired sum but it can trivially be transformed to whether there is a solution or not. Balint On Wednesday, August 15, 2012 1:13:32 AM UTC+2, John Holland wrote: > > I've been doing some programming exercises in Clojure, I've run into one I > don't know how to approach. If anyone can just give me the strategy to use > on this that'd be great. Here is the problem statement: > > Given an array of ints, is it possible to choose a group of some of the > ints, such that the group sums to the given target? > > > sample calls would be like: > > (groupSum [2, 4, 8] 10) → true > (groupSum [2, 4, 8] 14) → true > (groupSum [2, 4, 8] 9) → false > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/clojure?hl=en
