Backtracking — cheat sheet — Algorithms & Data Structures with Python

Backtracking builds an answer one choice at a time, recursing deeper while a partial solution can still work and undoing the last choice when it cannot.

Core idea

Backtracking: explore every sequence of choices by choosing, going deeper, then un-choosing to try alternatives.
Partial solution: an unfinished answer; some choices made, more to go.
Prune: cut a whole branch early once you can tell it cannot lead to a valid answer.
Built on recursion (a function calling itself).

The template: choose, explore, un-choose

def backtrack(path, choices):
    if is_complete(path):
        record(path)
        return
    for option in choices:
        if not allowed(option, path):
            continue          # prune
        path.append(option)   # 1. choose
        backtrack(path, ...)  # 2. explore
        path.pop()            # 3. un-choose

The path.pop() is the single most important line. Skip it and every branch leaks choices into the next.
It must run on every exit path from the recursion, so it sits right after the call, never inside an if.

Non-negotiable rules

Record a copy: result.append(path[:]), not path itself (a reference mutates to empty by the end).
Undo all state changed on the way down (both path and any used/cols marks), no exceptions.
Check the base case first, before the loop.
Create fresh state inside the function; never a mutable default arg (def f(path=[])).

Three problems

Problem	Choice per step	Answers	Time
Subsets	include or skip item; recurse with `i+1`	`2**n`	`O(n * 2**n)`
Permutations	pick an unused item (`used[]` array)	`n!`	`O(n * n!)`
N-Queens	column for this row; `safe()` prunes col/diag conflicts	varies	~`N**N` before pruning

Space (excluding output) is O(n): recursion depth plus the path.
Subsets pass i+1 so order does not matter; permutations reuse indices but block used ones.

Pruning

Cutting a branch removes its entire subtree from the search.
Does not change worst-case Big-O, but changes practical runtime dramatically (N-Queens: impossible vs instant).
Apply the strongest, cheapest check as early as possible, before sinking work into a bad path.

Pitfalls

Forgetting to un-choose: siblings inherit the leftover choice.
Restoring only some state: silently drops valid answers.
Storing the live list instead of a copy: all entries end up as the final state.
Shared mutable default argument: state leaks between runs.
Weak base case: never records, or never stops.