Быстрое решение проблемы суммы подмножества

Рассмотрим такой способ решения задачи о сумме подмножеств:

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

У меня это отсюда:

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

Существует также комментарий, в котором говорится, что можно сделать его «более эффективным».

Как?

Кроме того, есть ли какие-либо другие способы решения проблемы, по крайней мере такие же быстрые, как описанный выше?

Изменить

Меня интересуют любые идеи, которые привели бы к ускорению. Я нашел:

https://en.wikipedia.org/wiki/Subset_sum_problem#cite_note-Pisinger09-2

, в котором упоминается алгоритм линейного времени. Но бумаги у меня нет, может быть, вы, милые люди, знаете, как это работает? Возможно реализация? Может совсем другой подход?

Редактировать 2

Теперь есть продолжение:
Быстрое решение алгоритма суммирования подмножества от Писингера