0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Should set really be multiset? I.e. duplicates are allowed but not considered distinct? $\endgroup$ – Peter Taylor Apr 17 at 12:58
  • $\begingroup$ 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$ $\endgroup$ – Rby Apr 17 at 13:16
  • $\begingroup$ 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. $\endgroup$ – Peter Taylor Apr 17 at 13:22
  • $\begingroup$ I included $[1,6]$ and $[1,2,4]$ twice. Hope it's clearer now $\endgroup$ – Rby Apr 17 at 14:39
1
$\begingroup$

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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.