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.

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.

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.

When To Use It

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