BacktrackingAlgorithmaka recursive search, choose / explore / un-choose, backtracking template

Recursion & Backtracking

Solve a problem by reducing it to smaller copies of itself; backtracking explores a tree of partial choices and undoes each one after exploring it.

▶ VisualizePattern: Depth-First SearchPractice (6)
Progress

Overview

A recursive function calls itself on a strictly smaller input and combines the results. Two ingredients are mandatory: a base case that answers the smallest inputs directly, and a recursive case that makes measurable progress toward it. Without either, the function never returns.

Backtracking is recursion applied to search: build a candidate solution one decision at a time, recurse to complete it, and if the partial solution can no longer lead to a valid answer, undo the last decision and try the next option. The set of all partial solutions forms a recursion tree; backtracking is depth-first traversal of that tree, and pruning is refusing to enter subtrees that provably contain no answer.

Almost every enumeration problem — Subsets (Power Set), Permutations, Combinations (n choose k), N-Queens, Sudoku Solver, Word Search (Grid DFS) — is the same template with a different definition of "valid next choice".

recursionbacktrackingrecursion treepruningcall stackexhaustive search

Intuition

A mental model before the formal terms.

Picture a maze with many junctions. At each junction you pick a corridor, drop a breadcrumb, and walk on. Hit a dead end and you walk back to the last junction, pick up the breadcrumb, and try the next corridor. The breadcrumbs are your current path (the partial solution); picking one up is the "un-choose" step.

The recursion tree is the map of all corridors: the root is the empty path, each level is one more decision, leaves are complete candidates. A naive search visits every leaf. Pruning is noticing at a junction that every corridor beyond it is walled off — you turn back before walking down.

How it works

  1. Define the state: what has been chosen so far (usually a path array plus a used-set or the next index to consider).
  2. Base case: if the state is a complete solution, record or count it and return.
  3. Choose: for each candidate next choice that keeps the state valid (this check is the pruning), append it to the path and mark it used.
  4. Explore: recurse on the extended state.
  5. Un-choose: remove the choice from the path and unmark it, so the next iteration of the loop starts from exactly the same state.
  6. Recording a solution must copy the path (path[:], [...path]) — the path array is mutated afterwards by un-choose.

Why it works

Induction on the depth of the recursion: assuming every recursive call on a longer partial state correctly enumerates all completions of that state, the loop over valid next choices covers all completions of the current state exactly once, because each completion has a unique first choice.

Un-choose restores the invariant "state == the path from root to this node". Because every mutation made on the way down is reverted on the way up, siblings in the recursion tree see identical state.

Pruning is sound only if the rejected subtree truly contains no solution, i.e. validity is monotone: once a partial state is invalid, every extension of it stays invalid. Placing two queens on the same diagonal can never be repaired by adding more queens, so pruning there is safe.

Recognition

How to tell a problem wants this.

  • The problem asks for all solutions, all combinations/arrangements, or the number of valid configurations with small n (typically n ≤ 20, or a 9×9 board).
  • The answer is built from a sequence of decisions where each decision has a small set of options and there is a cheap validity check.
  • Constraints are exponential-looking (2^n, n!) and the input sizes are tiny; a DP would not apply because the state must remember the whole path.
  • Phrases: "generate all", "find any arrangement", "does a placement exist", "count the ways" with tiny bounds.
“connected groups” → Depth-First Search“all combinations” → Backtracking

Interactive visualization

Play, step, change the input. ← → and space work too.

Call stack (top first)
fact(5)
n=5
Recursion tree
fact(5)
1/15Call fact(5): a new frame is pushed on top of the stack. Nothing is computed yet because the answer depends on fact(4).
Call on the stackCall returned
PseudocodeLearn Recursion & Backtracking →
1fact(n):
2  if n <= 1: return 1        // base case
3  sub = fact(n - 1)          // recursive case
4  return n * sub
Variables
n5
depth1
Complexity
worst O(b^d · cost per node)
space O(d)
Speed

Pseudocode

1backtrack(state):
2  if state is complete:
3    record(copy of state)
4    return
5  for choice in candidates(state):
6    if not valid(state, choice): continue   # prune
7    apply(state, choice)                       # choose
8    backtrack(state)                           # explore
9    undo(state, choice)                        # un-choose

Implementations

1# Enumerate all bit-strings of length n with no two adjacent 1s.
2# Shows the choose / explore / un-choose skeleton with a pruning check.
3def no_adjacent_ones(n: int) -> list[str]:
4    out: list[str] = []
5    path: list[str] = []
6 
7    def backtrack() -> None:
81 · Base case
9        if len(path) == n:
10            out.append("".join(path))
11            return
12        for bit in ("0", "1"):
13            if bit == "1" and path and path[-1] == "1":
14                continue                # prune: would violate the rule
152 · Choose
16            path.append(bit)
173 · Explore
18            backtrack()
194 · Un-choose
20            path.pop()
21 
22    backtrack()
23    return out
24 
25 
265 · Plain recursion
27def factorial(n: int) -> int:
28    if n <= 1:
29        return 1
30    return n * factorial(n - 1)
Walkthrough
  1. backtrack is a nested function closing over path, out and n; it mutates path in place (no nonlocal needed since it never rebinds the name).
  2. The base case appends "".join(path), a fresh string, so the shared list can be reused.
  3. if bit == "1" and path and path[-1] == "1" prunes before any state change; path[-1] is the last element.
  4. append / recursive call / pop is the choose-explore-un-choose triple.
  5. factorial uses arbitrary-precision int, so there is no overflow; depth, not magnitude, is the limit.
Complexity (this implementation)
time O(n * F(n)) where F(n) is the number of valid strings · space O(n) recursion depth plus output

"".join(path) is O(n) per result; Python function calls are comparatively expensive, so deep backtracking is slower than in C++.

Language notes
  • CPython caps recursion at 1000 frames by default (RecursionError). Raise it with sys.setrecursionlimit(10**6) and, for very deep recursion, also threading.stack_size(...) because the C stack can still overflow.
  • CPython has no tail-call optimisation by design; math.factorial and functools.lru_cache are the pragmatic stdlib helpers.
  • Use nonlocal only when a nested function rebinds an outer variable (e.g. a counter); mutating a list does not require it.
Common mistakes in this language
  • Appending path (the shared list) to results instead of path[:] or list(path); every stored result then aliases the same object.
  • Hitting RecursionError on inputs of a few thousand and assuming the algorithm is wrong.
  • Rebinding path = path + [x] inside the helper, which creates a new local list and breaks the un-choose step.
Language differences that matter here
  • Recursion depth: CPython stops at 1000 frames by default (sys.setrecursionlimit raises it); V8 (JS/TS) throws RangeError around 10k frames; C++ is bounded only by the OS thread stack (~8 MB Linux/macOS, ~1 MB Windows) and overflows with a crash instead of an exception.
  • C++ must pass path and out by reference (string&, vector<string>&); JS/TS/Python closures capture the shared containers by reference automatically.
  • factorial overflows long long past 20! in C++, loses precision past 2^53 in JS/TS Number, and is exact in Python int.
  • No mainstream runtime here performs tail-call optimisation for backtracking; only C++ compilers may TCO simple tail recursion.

Complexity

Best
—
Average
—
Worst
O(b^d · cost per node)
Space
O(d)

b = branching factor, d = depth of the recursion tree. Output-sensitive: the number of leaves visited is bounded by the number of valid partial states, which pruning shrinks dramatically.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Enumerating or counting all configurations for small n where there is no overlapping-subproblem structure to exploit.
  • Constraint satisfaction: place items so that every pairwise constraint holds (N-Queens, Sudoku Solver).
  • Any problem where the natural recursive definition mirrors the answer (tree traversals, expression parsers, divide-and-conquer).
Avoid it when

Alternatives

Dynamic ProgrammingMemoization (Top-Down DP)Subset Generation with BitmasksDepth-First Search (DFS)Divide and Conquer

Common mistakes

  • Pushing path (the live reference) into the results instead of a copy — every recorded answer ends up empty or identical.
  • Forgetting the un-choose step, or un-choosing something different from what was chosen (e.g. visited set updated but not restored).
  • Base case placed after the loop, so the function keeps recursing past a complete solution.
  • Pruning with a check that is not monotone, which silently drops valid solutions.
  • Duplicate solutions when the input has repeated elements — sort and skip a[i] == a[i-1] when the previous copy was not used.

Interview patterns

Interview questions on this
Mock interviews

Example problems

N-QueenshardSubsetsmediumPermutationsmediumCombination SummediumWord SearchmediumSudoku Solverhard