Subset Sum Backtracking, in depth: the decision tree, sorted break and suffix-sum pruning, duplicate-free enumeration, branch and bound and measured limits

The decision tree

Give each element a decision: take it or leave it. Those decisions form a binary tree of depth n with 2ⁿ leaves. The plain search visits every node, which is 2ⁿ⁺¹ − 1 calls. For n = 30 that is about two billion calls. Brute force is still the reference implementation to test everything else against.

def subset_sum_naive(a, target):
    out, path = [], []
    def go(i, s):
        if i == len(a):
            if s == target:
                out.append(path.copy())
            return
        path.append(a[i]); go(i + 1, s + a[i]); path.pop()   # take a[i]
        go(i + 1, s)                                          # leave a[i]
    go(0, 0)
    return out

Backtracking means the same thing here as anywhere: choose, explore, unchoose. The path.pop() restores state on the way back up, so one list serves the whole search. The general pattern is explained in backtracking in depth. What makes subset sum fast in practice is not the recursion but the reasons to stop recursing early.

Two pruning rules and their preconditions

Restate the state as the index you are at and the amount still needed, remaining. With positive numbers, two facts let you cut whole subtrees.

1. Too big. If the next value is larger than remaining, taking it overshoots. If the list is sorted ascending, every later value is larger still, so you can stop the whole loop, not just skip one value.
2. Too small. If the sum of every value still available is less than remaining, no choice of them can reach the target. Precompute suffix sums so this is an O(1) test per node.

Both rules depend on all values being positive. With negative numbers, a later value can bring an overshooting sum back down, so neither cut is valid. Zeros are a quieter problem: they never change the sum, so every solution can be extended by any subset of zeros. Remove the zeros, solve, then report that each solution has 2^z variants for z zeros. For general signed input, either use a DP over offset sums when the range of totals is small, or use meet in the middle, which does not need sign assumptions.

The loop form below picks the next element to take, instead of a take-or-leave pair. It is equivalent, and it makes the ascending-order break and duplicate skipping easy to express.

The pruned search, with duplicates handled

def subset_sum_all(nums, target):
    """Every distinct subset of positive nums that sums to target."""
    a = sorted(nums)                                  # ascending: enables the break below
    suffix = [0] * (len(a) + 1)
    for i in range(len(a) - 1, -1, -1):
        suffix[i] = suffix[i + 1] + a[i]
    out, path = [], []

    def go(start, remaining):
        if remaining == 0:
            out.append(path.copy())
            return
        if suffix[start] < remaining:                 # too small: all that is left falls short
            return
        for i in range(start, len(a)):
            if i > start and a[i] == a[i - 1]:
                continue                              # same value at the same depth: same subtree
            if a[i] > remaining:
                break                                 # too big, and so is everything after it
            path.append(a[i])
            go(i + 1, remaining - a[i])
            path.pop()

    go(0, target)
    return out

The duplicate test is the subtle line. At one depth of the tree, choosing the first 1 or the second 1 from [1, 1, 2] leads to identical subtrees, so only the first is explored. The condition is i > start, not i > 0. Using i > 0 also blocks taking the second 1 directly after the first, which wrongly loses solutions such as [1, 1, 6]. The same rule appears in combination sum problems, covered in permutations and combinations.

To return only whether a solution exists, return True at the first hit and propagate it upward. To count without listing, return counts. The pruning is unchanged.

Worked example

Take [3, 34, 4, 12, 5, 2] and target 9. Sorted, the list is [2, 3, 4, 5, 12, 34] with suffix sums 60, 58, 55, 51, 46, 34, 0. The search goes:

1. Take 2, leaving 7. Take 3, leaving 4. Take 4, leaving 0: record [2, 3, 4].
2. Back at 2 and 3 with 4 remaining, the next value 5 is greater than 4, so the loop breaks.
3. Back at 2 with 7 remaining, take 4, leaving 3. The next value 5 is too big: break. Take 5, leaving 2: break. The next value 12 is greater than 7, so the loop at this level breaks too.
4. At the root, take 3, leaving 6. Taking 4 leaves 2 and taking 5 leaves 1; both die immediately.
5. Take 4, leaving 5. Take 5, leaving 0: record [4, 5].
6. Take 5, leaving 4. The suffix sum after 5 is 46, so the too-small test passes, but 12 is too big. Then 12 at the root is greater than 9, so the root loop breaks.

Counting calls in the instrumented version gives 12 nodes, against 127 for the plain take-or-leave tree. For [10, 1, 2, 7, 6, 1, 5] with target 8, the pruned search makes 17 calls and returns the four distinct solutions [1, 1, 6], [1, 2, 5], [1, 7] and [2, 6]; the plain tree makes 255 calls and reports [1, 7] and [1, 2, 5] twice each because of the repeated 1. Both counts come from running the code above with a call counter, and the outputs were checked against brute force on 2,000 random positive inputs.

Best fit with branch and bound

Often there is no exact solution, and the real question is the best fit: the largest total not exceeding a budget, such as filling a disk, a container or a time slot. That is branch and bound. Keep the best total found so far, the incumbent, and cut any branch whose optimistic bound cannot beat it.

def closest_under(nums, target):
    a = sorted(nums, reverse=True)                    # big items first: good incumbents early
    suffix = [0] * (len(a) + 1)
    for i in range(len(a) - 1, -1, -1):
        suffix[i] = suffix[i + 1] + a[i]
    best = 0

    def go(i, s):
        nonlocal best
        best = max(best, s)
        if best == target or i == len(a):
            return
        if s + suffix[i] <= best:                     # bound: even taking everything cannot win
            return
        if s + a[i] <= target:
            go(i + 1, s + a[i])                       # take
        go(i + 1, s)                                  # leave

    go(0, 0)
    return best

This version sorts descending on purpose. Large items first find a good incumbent quickly, which makes the bound bite sooner. That also means the ascending-order break is no longer available: with a descending sort, a value that does not fit says nothing about the smaller values after it, so the code tests each item instead. Stopping as soon as the incumbent equals the target is the most valuable line in practice. This is the same idea used in branch and bound for knapsack, where items also have values.

What pruning buys, measured

Pruning helps most when solutions are plentiful or numbers are small relative to the target. It helps least on the hardest instances: many large random values with no exact solution. Measured on this machine in CPython, with 24 random integers between one million and one billion and a target of half their total, subset_sum_all found no solution after 7,454,831 calls, about 22% of the 33,554,431-node full tree, in roughly 12 seconds. With 30 such values, closest_under made 17,766,979 calls in about 14 seconds and finished 5 below the target. Your timings will differ, but the shape will not: on hard instances pruning removes a constant factor, not the exponent.

Subset sum is NP-complete, so no method avoids exponential worst cases in general. The DP is pseudo-polynomial: fast when T is small, useless when T is huge. Pick by which of n or T is small.

Memoising dead ends

The pruned search can reach the same state, the same index with the same amount still needed, along different paths. In sorted [1, 2, 3, 4, ...], taking 1, 2 and 4 and taking 3 and 4 both stop just after the 4 with 7 used. If that state failed once, it will fail again, so remember it.

def subset_sum_exists(nums, target):
    a = sorted(nums)
    suffix = [0] * (len(a) + 1)
    for i in range(len(a) - 1, -1, -1):
        suffix[i] = suffix[i + 1] + a[i]
    dead = set()                                      # (start, remaining) states known to fail

    def go(start, remaining):
        if remaining == 0:
            return True
        if suffix[start] < remaining or (start, remaining) in dead:
            return False
        for i in range(start, len(a)):
            if i > start and a[i] == a[i - 1]:
                continue
            if a[i] > remaining:
                break
            if go(i + 1, remaining - a[i]):
                return True
        dead.add((start, remaining))
        return False

    return go(0, target)

This is the DP table again, filled lazily and only where the search actually goes. It pays off when remainders repeat, which happens when values are small or share common factors, such as prices that are all multiples of five cents. With large random values almost no two paths leave the same remainder, so the set only costs memory. Cap its size, or measure the hit rate on your own data before keeping it. For existence and counting, memoisation is complete. When you must list every solution, only remembered failures help; a remembered success does not, because each path to it produces different output.

Bugs that break solutions

What to do next

1. Implement subset_sum_naive and subset_sum_all and check them against each other on random positive inputs.
2. Add a call counter and reproduce the 12-node and 17-node counts from the worked examples.
3. Delete the suffix-sum test and measure how the node count changes on 20 random values.
4. Change the duplicate test to i > 0 and find the input that breaks it.
5. Implement closest_under and add a time limit that returns the incumbent.
6. Time your search against meet in the middle for n = 30 and n = 40 and record where it stops being usable.