Thanks for all the help! On Tuesday, August 14, 2012 7:38:58 PM UTC-4, Andy Fingerhut wrote: > > 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 clo...@googlegroups.com <javascript:> > 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 <javascript:> > 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
