Backtracking

When to use

Use when you must generate all combinations, permutations, subsets, or valid paths through a decision tree. If the problem says 'return all possible' or 'find all valid', think backtracking.

Core intuition

At each step, make a choice. Recurse with that choice. Undo the choice after recursing. Try the next option. You're building a decision tree and pruning branches that can't lead to valid answers.

Template

def backtrack(result, current, options, start):
    if is_complete(current):
        result.append(current[:])
        return
    for i in range(start, len(options)):
        if not is_valid(current, options[i]):
            continue
        current.append(options[i])        # choose
        backtrack(result, current, options, i + 1)  # recurse
        current.pop()                     # un-choose

result = []
backtrack(result, [], nums, 0)

Suggested problems