Find all subsets with a given sum

Question

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],[7]$. 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.

Answer 1

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[0] == 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.

def calculate_masks(elements, target_sum):
    masks_of_interest = (1 << (target_sum + 1)) - 1
    accumulated_mask = 1
    accumulated_mask = []
    for element in elements:
        accumulated_mask = (accumulated_mask | (accumulated_mask << element)) & masks_of_interest
        accumulated_masks.append(accumulated_mask)

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[0] == 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):
    masks = calculate_masks(elements, target_excess)
    return subsets_having_sum_impl(elements, target_excess, masks)