That is a very complicated way to code this. Here is the quick and dirty technique that I have been using on lots of Project Euler problems:<p><pre><code> def subset_summing_to_zero (activities):
subsets = {0: []}
for (activity, cost) in activities.iteritems():
old_subsets = subsets
subsets = {}
for (prev_sum, subset) in old_subsets.iteritems():
subsets[prev_sum] = subset
new_sum = prev_sum + cost
new_subset = subset + [activity]
if 0 == new_sum:
new_subset.sort()
return new_subset
else:
subsets[new_sum] = new_subset
return []
</code></pre>
(I could easily make this more efficient.)
The challenge was:<p>---<p>We get a list of up to 50 activities and an associated calorie value for each (either positive or negative), we need to find a subset of activities where the sum of all the calorie values is zero.<p>---<p>Did anyone else here immediately think to write a function hard coded to return the empty set?
I did a very similar investigation 5 years ago, to find the optimal way to fill-up a DVD from a set of files of various sizes (more than a DVD's worth). Have a look:<p><a href="http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html" rel="nofollow">http://users.softlab.ece.ntua.gr/~ttsiod/fillupDVD.html</a>
Here is my Perl code for the diet puzzle, as well as sorting it splits the set into positive and negative subsets: <a href="https://gist.github.com/805894" rel="nofollow">https://gist.github.com/805894</a>
So, for the problem, we are given some positive integer n and, for i = 1, 2, ..., n, numbers a(i).<p>So, we seek x(i) to solve<p><pre><code> min ( x(1) a(1) + x(2) a(2) + ... + x(n) a(n) )^2
x(1) + x(2) + ... + x(n) >= 0
subject to x(i) = 0, 1
</code></pre>
So this is a 0-1 integer quadratic program with one linear constraint.<p>So for a reasonably practical solution, omit the 0-1 constraint and attack the problem as just a quadratic program.<p>Then for the 0-1 constraint, do standard branch and bound.