title: Fast solution to Subset sum
body: <p>Consider this way of solving the Subset sum problem:</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>
  
  <p>I have it from here:</p>
  
  <p><a href="http://news.ycombinator.com/item?id=2267392" rel="nofollow noreferrer">http://news.ycombinator.com/item?id=2267392</a></p>
  
  <p>There is also a comment which says that it is possible to make it "more efficient".</p>
  
  <p>How?</p>
  
  <p>Also, are there any other ways to solve the problem which are at least as fast as the one above?</p>
  
  <p><strong>Edit</strong></p>
  
  <p>I'm interested in any kind of idea which would lead to speed-up. I found:</p>
  
  <p><a href="https://en.wikipedia.org/wiki/Subset_sum_problem#cite_note-Pisinger09-2" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Subset_sum_problem#cite_note-Pisinger09-2</a></p>
  
  <p>which mentions a linear time algorithm. But I don't have the paper, perhaps you, dear people, know how it works? An implementation perhaps? Completely different approach perhaps?</p>
  
  <p><strong>Edit 2</strong></p>
  
  <p>There is now a follow-up:<br>
  <a href="https://stackoverflow.com/questions/9962568/fast-solution-to-subset-sum-algorithm-by-pisinger">Fast solution to Subset sum algorithm by Pisinger</a></p>