Skip to main content

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 2n2^n subsets. For nonnegative integer targets, a decision-only dynamic program runs in pseudo-polynomial O(nT)O(nT) time, where TT is the target, trading numeric magnitude for state count.

Source​