Subset Sum by Backtracking

The 0/1 subset-sum decision problem asks whether some subset of the given items sums to a target. Each input position may be selected at most once. Enumerating all witnesses is a larger output problem than deciding existence.

For positive integers, sorted order permits useful pruning:

def subset_sum_witnesses(values: list[int], target: int) -> list[list[int]]:
    values = sorted(values)
    result: list[list[int]] = []
    path: list[int] = []

    def visit(start: int, remaining: int) -> None:
        if remaining == 0:
            result.append(path.copy())
            return
        for i in range(start, len(values)):
            if i > start and values[i] == values[i - 1]:
                continue
            if values[i] > remaining:
                break
            path.append(values[i])
            visit(i + 1, remaining - values[i])
            path.pop()

    visit(0, target)
    return result

The increasing start index enforces 0/1 use and canonical order. Skipping equal values at the same depth removes duplicate value-multisets.

Boundaries

• The value > remaining pruning is sound only under the positive-value assumption; negative values invalidate it.
• Passing i instead of i + 1 changes the problem to unlimited reuse.
• Generating permutations of a subset is not subset sum; order should not create a new solution.

Worst-case search explores $2^n$ subsets. For nonnegative integer targets, a decision-only dynamic program runs in pseudo-polynomial $O(nT)$ time, where $T$ is the target, trading numeric magnitude for state count.

Witness trace and output cost

For [1,1,2,3] and target 4, choosing 1 leaves 3. Choosing the next 1 then leaves 2 and finds [1,1,2]; choosing 3 instead finds [1,3]. The second root-level 1 is skipped because it would repeat the same value-multisets. The branch beginning with 2 cannot finish with the remaining 3 and is pruned. Thus the complete output is [[1,1,2],[1,3]].

With positive integers, target zero has exactly the empty witness [[]]; a negative target has none. Empty input behaves the same way. Zeros are outside this contract: returning at remaining zero would miss [0] and other extensions. Negative values also break the early-return/pruning argument; for example [-3,-2] can sum to −5 even though its first sorted value exceeds the target. For signed inputs, use include/exclude recursion over positions and test the sum only at the end, or prove signed lower/upper bounds.

The increasing index bounds depth by n. Auxiliary state, including the sorted copy and stack, is O(n); storing and copying witnesses adds up to O(n·2ⁿ) time and output space in the worst case. The O(nT) decision DP mentioned above assumes nonnegative integer item values as well as a nonnegative target.

assert subset_sum_witnesses([1, 1, 2, 3], 4) == [[1, 1, 2], [1, 3]]
assert subset_sum_witnesses([], 0) == [[]]
assert subset_sum_witnesses([], 1) == []

Source

• Stanford CS106B: Backtracking

My reading · Opened notes are remembered in this browser.