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