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
First solution:
(defn groupSum [l x]
(or (zero? x) ; we have won!
(and (not (< x 0)) ; we can't win
(not (empty? l)) ; lost!
(or (groupSum (rest l) (- x (first l)))
(recur (rest l) x)
The "we
Ended up with the following wondering if loop/recur is possible in this
case?
(defn groupSum [a x] (cond
(= (count a) 0) false
(= (first a) x) true
(> (first a) x) (if (> (count a) 1) (groupSum (rest
a) x) false)
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 number
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
> On Tue, 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.
the other way of looking at it is that the recursion just quits once
the sum it is carrying
On Tue, 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.
in the stupidest approach that is just the same thing as "all of the
numbers in the vector" wit
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 ca
sorry "take the first#" actually is meant to be worded as, "in turn,
take out 1 of each of the #s, and recurse on what remains" so that you
are doing the permutations at each level of the recursion/tree.
On Tue, Aug 14, 2012 at 4:15 PM, Raoul Duke wrote:
> ¿
> take the first #.
> subtract that fr
¿
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 wrote:
> I've been doing s
10 matches
Mail list logo
