The Backtracking Template

Backtracking is recursion with the ability to undo a choice. The template has four parts that appear in every backtracking function.

First, the state. This is the data the search carries with it, such as the current combination, the remaining target, or a set of used positions. Second, the choice loop, which iterates over the options available at this level. Third, the explore step, which makes the choice, updates the state and recurses. Fourth, the undo step, which restores the state to what it was before the choice, so the next iteration starts from a clean slate.

def search(state, remaining):
    if remaining == 0:
        record(state)
        return
    for option in options(state):
        apply(option)
        search(new_state, new_remaining)
        undo(option)

The undo step is the one that gets forgotten, and it is the one that decides whether the algorithm is correct. If you forget to undo, the state leaks between branches and you will produce wrong answers or miss valid ones.

The mechanism is that the recursion explores a tree of choices. The number of nodes in that tree is what determines the running time, and pruning is the art of not visiting the nodes that cannot lead to a valid answer. A branch is pruned when the remaining target is already zero, when an option exceeds what is left, or when the remaining options cannot possibly fill the gap.

The trade-off to name is that the output size is often the bound. For problems like subsets, permutations and combination sum, the number of valid answers is enormous, so the search cost is at least the cost of producing them. Pruning does not change that lower bound, it only removes the wasted branches. And the state has to be copied when you record an answer, because the list you are carrying keeps changing as the search continues.

At each level you choose whether to include the next element, and you record the current set at every level, because every level of the decision tree is itself a valid subset.

def subsets(values):
    result = []
    current = []

    def backtrack(start):
        result.append(list(current))
        for i in range(start, len(values)):
            current.append(values[i])
            backtrack(i + 1)
            current.pop()

    backtrack(0)
    return result


print(subsets([1, 2]))

The output is the empty list, then 1, then 1 and 2, then 2. Those are all four subsets of a two-element list.

The mechanism is that recording happens at the top of the function rather than at the bottom. The bottom of the function is where the choice list runs out, and by then every subset has already been recorded on the way down. That is the pattern for enumeration problems where every partial answer counts.

The trade-off to name is the copy on record. The result list stores a copy of the current combination rather than the list itself, because the same list is mutated as the search continues. If you stored the list itself, every entry in the result would point at the same object and they would all end up showing the final state. The other detail worth naming is that the loop starts at the index passed in, so elements are only ever added in increasing order, which is what prevents the same subset being produced twice in a different order.

The same four parts, with the pruning added as a guard at the top of the choice loop.

def combination_sum(candidates, target):
    results = []
    current = []

    def backtrack(start, remaining):
        if remaining == 0:
            results.append(list(current))
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            current.append(candidates[i])
            backtrack(i, remaining - candidates[i])
            current.pop()

    backtrack(0, target)
    return results


print(combination_sum([2, 3, 6, 7], 7))

The output is 2, 2, 3 and then 7. The recursion starts at index zero each time so the 2 can be used twice, and the candidate list is assumed to be sorted.

The mechanism is that the pruning guard turns the choice loop into a bounded one. When a candidate is larger than the amount still needed, it cannot be part of any solution from this point, and because the list is sorted every later candidate is larger still, so the break abandons the whole rest of the loop. Without it the search would descend into branches that can never succeed, exploring combinations that already overshoot the target.

The trade-off to name is that the break relies on the candidate list being sorted, so you must sort it yourself before starting. If you cannot assume sorted input, the guard becomes a continue instead of a break, which prunes the same branches but keeps scanning the rest of the list, and the recursion is correspondingly slower. A stronger prune also checks whether the remaining amount can be filled at all using the candidates that are left, using a suffix sum, and that removes whole subtrees rather than single branches.