Find all subsets with a given sum

How to choose from a set of positive numbers all the subsets that sum to some number x? For example if the set $$S=[1,1,2,3,4,5,6,7]$$ and I'm searching for all the subsets that sum to $$7$$ I would have $$[1,6],[1,6],[2,5],[1,1,5],[3,4],[1,2,4],[1,2,4],$$. What I'm trying to do now is to generate all the possible tuples of $$\{0,1\}$$, so for the set $$S$$ which has length $$7$$ I have: $$\{0, 0, 0, 0, 0, 0, 0\}, \{0, 0, 0, 0, 0, 0, 1\}, \{0, 0, 0, 0, 0, 1, 0\},...$$, multiply the element of tuples of $$0$$ and $$1$$ by the corresponding element of the set $$S$$ and check if the sum is equal to $$7$$.

I got the idea of the tuples in this question: N subsets with a given sum? However that problem is slightly different from mine so I was wondering if there's a way to speed things up.

• Should set really be multiset? I.e. duplicates are allowed but not considered distinct? – Peter Taylor Apr 17 at 12:58
• Duplicates should be considered distinct. To be clearer $[1,6]$ should be $[1,6]$ in which $1$ is the first element of set $S$ and $[1,6]$ in which $1$ is the second element of set $S$ – Rby Apr 17 at 13:16
• That would be much clearer if you included $[1,6]$ and $[1,2,4]$ twice each in the list of expected output from the example. – Peter Taylor Apr 17 at 13:22
• I included $[1,6]$ and $[1,2,4]$ twice. Hope it's clearer now – Rby Apr 17 at 14:39

Each subset of $$S$$ either contains the first element or doesn't. So we can implement a generic enumeration of subsets which match a predicate as (code given in Python but untested):

def subsets_matching_predicate(elements, predicate, included = []):
if len(elements) == 0:
if predicate(included):
yield included
else:
for subset in subsets_matching_predicate(elements[:-1], predicate, included):
yield subset
for subset in subsets_matching_predicate(elements[:-1], predicate, included + elements[-1:]):
yield subset

This is essentially what your approach does.

But the sum is monotone, since the numbers are restricted to be positive, so this can be optimised.

def subsets_having_sum(elements, target_sum, included = [], included_sum = 0):
if included_sum > target_sum:
return

if len(elements) == 0:
if included_sum == target_sum:
yield included
else:
for subset in subsets_having_sum(elements[:-1], target_sum, included, included_sum):
yield subset
for subset in subsets_having_sum(elements[:-1], target_sum, included + elements[-1:], included_sum + elements[-1]):
yield subset

We can also simplify in various ways:

• Pass target_sum - included_sum instead of two variables
• Accumulate on the way out rather than the way in
• Once we hit the target, we don't need to keep going
def subsets_having_sum(elements, target_excess):
if len(elements) > 0:
for subset in subsets_having_sum(elements[:-1], target_excess):
yield subset

if elements == target_excess:
yield elements[-1:]
else:
for subset in subsets_having_sum(elements[:-1], target_excess - elements[-1]):
yield elements[-1:] + subset

There's a further optimisation whereby we pre-calculate the numbers which can be reachable with each sublist, and don't bother calling in if they're not reachable. The memory/speed tradeoff depends on the expected length of elements and value of target_sum.

masks_of_interest = (1 << (target_sum + 1)) - 1
for element in elements:

def subsets_having_sum_impl(elements, target_excess, masks):
if len(elements) > 0 and (masks[-1] >> target_excess) & 1:
for subset in subsets_having_sum(elements[:-1], target_excess, masks[:-1]):
yield subset

if elements == target_excess:
yield elements[-1:]
else:
for subset in subsets_having_sum(elements[:-1], target_excess - elements[-1], masks[:-1]):
yield elements[-1:] + subset

def subsets_having_sum(elements, target_excess):