An additional step on top of Raoul's: Take the first #, subtract it from the goal, recursively ask if the remaining #s can sum to the now-lesser goal. If so, return yes, or the set of numbers that worked (which should include whatever was returned from the recursive call, plus the first #)
If not, recursively ask if the remaining #s can sum to the original goal. If so return yes, or the set of numbers that worked (which does not include the first #) In the worst case, that will try all 2^n possible subsets of the collection of numbers, and then return false. There are dynamic programming methods that work faster if the sum of the numbers is small enough, but require holding in memory an array of at least N bits, where N is the target. Andy On Aug 14, 2012, at 4:17 PM, John Holland wrote: > I thought of doing something like that, but part of the requirements is that > the sum could be achieved with *some" of the numbers in the vector. > > On Tuesday, August 14, 2012 7:15:27 PM UTC-4, raould wrote: > ¿ > take the first #. > subtract that from the goal. > now ask if the remaining #s can sum to the now-lesser goal. > lather rinse repeat. > don't forget a base case. > watch your cpu heat very quickly up on even slightly longer lists. > ? > > On Tue, Aug 14, 2012 at 4:13 PM, John Holland <jbho...@gmail.com> 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 clo...@googlegroups.com > > Note that posts from new members are moderated - please be patient with > > your > > first post. > > To unsubscribe from this group, send email to > > clojure+u...@googlegroups.com > > For more options, visit this group at > > http://groups.google.com/group/clojure?hl=en > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with your > first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
