Enumerating all subsets with sum at most S

  algorithm, python-3.x

What is an efficient way to enumerate all subsets of a given list L of numbers, such that the sum of all numbers in the set is at most a constant S?

One option is to use the recipe for powerset from itertools, and then filter by the sum, like this:

for subset in powerset(L):
    if sum(subset) <= S:
        yield subset

But this may be very wasteful, since the number of subsets may be very large, and only a small number of them have a sum of at most S. What is a more efficient way to do this?

Source: Python-3x Questions

LEAVE A COMMENT