Fast solution to Subset sum
Consider this way of solving the Subset sum problem:

    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 []

I have it from here:

http://news.ycombinator.com/item?id=2267392

There is also a comment which says that it is possible to make it "more efficient".

How?

Also, are there any other ways to solve the problem which are at least as fast as the one above?
Fast solution to Subset sum
===

Consider this way of solving the Subset sum problem:

    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 []

I have it from here:

http://news.ycombinator.com/item?id=2267392

There is also a comment which says that it is possible to make it "more efficient".

How?

Also, are there any other ways to solve the problem which are at least as fast as the one above?