How to Solve the Subset Sum Problem with Backtracking

The subset sum problem asks whether a collection of numbers contains a subset whose values add up to a specified target. For example, given [3, 7, 10, 12] and a target of 19, the answer is yes because 7 + 12 = 19. The task may also require returning the selected values rather than only reporting whether a solution exists.

Backtracking is a natural way to solve this kind of combinatorial search problem. At each position, the algorithm chooses between including and excluding the current number, then reverses that choice when a branch cannot produce a valid answer. This method is easy to explain, adaptable to several variations, and useful for learning how recursive search explores a decision tree.

Why Subset Sum Is A Search Problem

For every element, there are two possibilities: include it in the candidate subset or leave it out. With n values, this creates up to 2^n possible subsets. A direct approach could generate every subset and calculate its sum, but backtracking visits these choices in a structured depth-first order and can stop as soon as it finds a solution.

The recursion can be viewed as a binary tree. The left branch might include the current value, while the right branch skips it. This is closely related to the search strategy explained in breadth-first graph traversal, although subset sum usually benefits from depth-first exploration because a complete candidate can be built along one path before trying alternatives.

Suppose the input is [2, 5, 8] and the target is 10. The algorithm first examines choices involving 2, then continues with 5 and 8. If the running total becomes 10, it succeeds. If the selected numbers exceed the target and all values are non-negative, that branch can be abandoned immediately.

State Representation And Recursion

A useful recursive function needs enough state to describe the current search position. The common parameters are the index of the next value, the remaining sum, and the list of values selected so far. The remaining sum is often clearer than a running total: selecting a number simply reduces the amount still required.

There are two important base cases. If the remaining sum is zero, the algorithm has found a valid subset. If the index reaches the end of the input before the remaining sum becomes zero, that branch has failed. The recurrence then tries the include branch followed by the exclude branch.

search(index, remaining, chosen):
    if remaining == 0:
        return chosen

    if index == length(numbers):
        return failure

    value = numbers[index]

    result = search(index + 1,
                    remaining - value,
                    chosen + [value])

    if result is successful:
        return result

    return search(index + 1,
                  remaining,
                  chosen)

The chosen + [value] expression creates a new list, which is convenient for teaching and for avoiding accidental mutations. A more performance-conscious implementation can append the value, recurse, and then remove it before exploring the next branch. That append-and-pop pattern is the classic backtracking technique.

Pruning The Search Tree

Pruning means proving that a branch cannot produce a solution and stopping before exploring its descendants. For non-negative input values, the simplest rule is to stop when remaining < 0. Adding more values can only increase the selected total, so the target cannot be reached from that branch.

Sorting the numbers can make this rule more effective. If the values are processed from largest to smallest, a branch may exceed the target early. If they are processed from smallest to largest, the algorithm may encounter several small combinations before reaching a useful total. The better order depends on the data, but sorting costs O(n log n) and can improve practical performance.

Pruning must match the assumptions of the input. The remaining < 0 rule is incorrect when negative numbers are allowed because a later negative value could bring the total back down. With mixed positive and negative integers, the safe stopping conditions are more limited. Duplicate values can also create repeated branches, so sorting and skipping equal values at the same recursion depth can help when the task asks for unique combinations.

Python Implementation

The following implementation returns one matching subset and assumes that all input numbers are non-negative. It uses an index to ensure that each list position is considered once.

def subset_sum(numbers, target):
    numbers = sorted(numbers)

    def search(index, remaining, chosen):
        if remaining == 0:
            return chosen.copy()

        if index == len(numbers) or remaining < 0:
            return None

        value = numbers[index]

        chosen.append(value)
        result = search(index + 1, remaining - value, chosen)
        chosen.pop()

        if result is not None:
            return result

        return search(index + 1, remaining, chosen)

    return search(0, target, [])

For example, subset_sum([3, 7, 10, 12], 19) may return [7, 12]. The exact result can vary if the input contains several valid subsets, because the recursive order determines which solution is discovered first.

The pop() call is essential. It restores chosen to the state it had before the include branch, allowing the exclude branch to work with the correct partial subset. Omitting it causes values from failed branches to leak into later candidates, producing incorrect results that can be difficult to diagnose.

Handling Variations And Edge Cases

An empty target of zero should usually return an empty subset because selecting no elements produces a sum of zero. An empty input with a non-zero target should fail. If the problem requires at least one selected value, that rule must be added separately because the standard mathematical definition accepts the empty subset for target zero.

When the input contains repeated values, decide whether equal values at different positions count as distinct. For [2, 2, 3], the two 2s may represent separate items, so selecting both is valid. If the goal is to return unique value combinations, sort the input and skip a value when it equals the previous value at the same recursion level.

Some versions ask for every valid subset rather than the first one. In that case, the base case appends a copy of chosen to a results list instead of returning immediately. Other versions ask whether a solution exists, where a Boolean result avoids storing the selected values. The same decision tree supports all of these formats.

Subset sum also appears in practical planning tasks. A café in Melbourne might select supplier orders that fit an exact weekly budget in Australian dollars, while a Brisbane community group could choose equipment packages that use a fixed grant amount. These examples are simplified, but they demonstrate why the distinction between “any solution” and “all solutions” matters.

Complexity And Practical Limits

Without pruning, backtracking has a worst-case time complexity of O(2^n) because each of the n values can be included or excluded. Sorting adds O(n log n), but that cost is insignificant beside exponential exploration for large n. If the algorithm stores a selected subset at each recursive level, the auxiliary recursion space is O(n), excluding the returned result.

This exponential bound makes plain backtracking suitable for small or moderate input sizes, especially when a solution is found early or pruning removes many branches. For larger targets and non-negative integers, dynamic programming can be preferable. A table indexed by achievable sums gives pseudo-polynomial time of O(nT), where T is the target, and a bitset implementation can be faster in practice.

The distinction is useful in scheduling and resource allocation. A project team in Sydney could use subset sum to select tasks whose durations fit a fixed work window, while the broader scheduling relationship is explained by the critical path method. Subset sum handles a precise combination constraint; critical path analysis focuses on dependencies and the longest sequence of activities.

For production software, input size should be checked before choosing the algorithm. A small interview-style instance may be ideal for recursion, whereas a large target, strict response-time requirement, or user-facing application may need dynamic programming, integer programming, or a greedy approximation. In Australia, a system handling customer purchase data should also consider obligations under the Privacy Act 1988 when storing or logging inputs, even though the mathematical algorithm itself does not process personal information by necessity.

A Reliable Implementation Workflow

A disciplined workflow helps prevent subtle errors in recursive search. Test the empty input, target zero, a target larger than the total sum, duplicate values, and a case with more than one valid subset. Also include an impossible target so that every branch must fail cleanly.

When working through coding exercises, it can help to compare the recursive reasoning with other algorithm explanations in the problem-solving collection. Trace a small example by hand, draw the include and exclude branches, and verify that each recursive call advances the index exactly once.

Practical recommendations for this problem include:

• State whether numbers may be negative, repeated, or zero before writing pruning rules.
• Use remaining == 0 as the success condition and return a copy of the selected path.
• Sort non-negative inputs when early termination or duplicate handling can benefit from order.
• Use append-and-pop backtracking so each branch receives the correct candidate state.
• Choose dynamic programming when the target is moderate but the number of values is too large for 2^n search.
• Test both existence-only and solution-returning versions against hand-checked examples.
• Document whether the function returns one subset, every subset, or only a Boolean answer.

Backtracking remains valuable even when another method is faster for large cases. It exposes the underlying choices clearly, supports customised constraints, and provides a strong foundation for understanding recursive algorithms, pruning, and state-space search.