Backtracking

Backtracking explores choices step by step and returns when a partial choice cannot lead to a valid answer.

It is a structured way to search through combinations, permutations, constraints, and decision trees.

Core Idea

Backtracking builds a partial solution. At each step, it tries a choice, recurses, and then undoes the choice before trying the next one.

The important optimization is pruning: if a partial solution already violates a rule, the algorithm stops exploring that branch.

The backtracking shape is choose, explore, unchoose. That shape lets one shared current list represent the partial solution while recursion moves through the decision tree.

Function Contracts

subsets(values) accepts a sequence and returns a list of all subsets represented as lists. The number of returned subsets is 2 ** len(values).

permutations(values) accepts a sequence and returns every ordering of the input values. The number of returned permutations is len(values)!, so this is only practical for small inputs.

Python Example

def subsets(values):
    result = []
    current = []
 
    def search(index):
        if index == len(values):
            result.append(current.copy())
            return
 
        search(index + 1)
 
        current.append(values[index])
        search(index + 1)
        current.pop()
 
    search(0)
    return result

The append chooses an item. The pop undoes that choice.

The Choose-Explore-Unchoose Shape

Many backtracking solutions follow the same control flow: choose one option, explore everything under that option, then undo the option before trying the next one.

Permutations show the shape with concrete code:

def permutations(values):
    result = []
    current = []
    used = [False] * len(values)
 
    def search():
        if len(current) == len(values):
            result.append(current.copy())
            return
 
        for i, value in enumerate(values):
            if used[i]:
                continue
 
            used[i] = True
            current.append(value)
            search()
            current.pop()
            used[i] = False
 
    search()
    return result

current.append(value) chooses. The recursive call explores. current.pop() and used[i] = False undo the choice so the next branch starts from a clean state.

Pruning

Pruning means refusing to explore a branch once it cannot succeed.

For example, in a combination-sum problem, if all numbers are positive and the current sum is already greater than the target, adding more numbers cannot fix it. That branch can stop immediately.

Pruning does not change the set of valid answers. It only avoids work that cannot produce one.

Complexity

The cost depends on how many branches are actually explored. Generating all subsets of n values takes O(2^n) time because there are 2^n subsets to output.

Generating all permutations takes O(n!) branches, and each recorded permutation has length n, so the output itself is large.

Pruning can make a practical problem much faster, but the worst-case search space may still be exponential.

Failure Example

If current.pop() is forgotten in the subset example, the choice made in one branch leaks into the next branch. The result then contains combinations that do not match the intended choice path.

Backtracking code is correct only when each recursive call leaves shared mutable state exactly as it found it before returning.

Common Confusions

Backtracking is not just recursion. It is recursion plus controlled choice, constraint checking, and undoing state.

Forgetting to undo a choice is a common bug. Shared mutable state must be restored before the function returns to the previous level.

Another common bug is appending current directly to the results. Use current.copy() when recording a list, because current will continue changing after recursion returns.

When To Use It

Use backtracking for permutations, subsets, combinations, constraint satisfaction, board problems, and any problem where choices form a tree of possibilities.

Backtracking is usually appropriate when the output itself may be large or when constraints can prune most branches.

The Main Point

Backtracking explores a choice tree while carefully undoing each choice. It is useful when constraints can prune branches before the full search space is explored.