Backtracking

TL;DR

Backtracking is depth-first search over a tree of choices. At every node you make a decision, recurse into the subtree that decision opens up, then undo the decision before trying the next one. The whole pattern collapses into a four-line skeleton — choose → recurse → unchoose — that generates subsets, permutations, combinations, N-queens, sudoku boards, and every constraint-satisfaction problem that doesn’t have overlapping subproblems.

The shape of the recursion tree is fixed by the problem (binary for include/exclude, n-ary for “pick one of the remaining”, etc.), but the runtime is determined almost entirely by your pruning. Without it, backtracking is just exponential brute force with extra steps. With it, N-queens for n=20 finishes in milliseconds even though the naive permutation count is 20! ≈ 2.4 × 10¹⁸.

The core mental model: think of the recursion as walking a tree. Each recursive call is “go down one level”; each return is “back up one level and try the next sibling”. The unchoose step is what makes the parent’s state look identical before and after the recursive call — that’s the invariant that keeps siblings independent.

When to reach for it

Signals that backtracking is the right hammer:

• The problem asks you to enumerate all valid configurations — every subset, every permutation, every way to place pieces on a board.
• The problem is a constraint-satisfaction search — N-queens, sudoku, graph coloring, word-break — where you build a candidate solution incrementally and abandon branches the moment they violate a rule.
• You need any one solution to a search problem with no closed-form shortcut and no overlapping subproblems (that last bit matters — if subproblems overlap, switch to DP).
• The state space is tree-shaped, not DAG-shaped. Each path of choices is unique and you don’t revisit equivalent partial solutions.

If your subproblems overlap (same partial state reached by different choice sequences), pure backtracking will redo work exponentially. Memoise it (top- down DP) or rewrite as bottom-up DP.

Flavor 1 — subsets (LC 78)

Generate all 2ⁿ subsets of a list using the include/exclude tree: at index i, either take nums[i] or don’t.

def subsets(nums: list[int]) -> list[list[int]]:
    res, path = [], []

    def backtrack(i: int) -> None:
        if i == len(nums):
            res.append(path.copy())   # deep-copy: path keeps mutating
            return
        # choice 1: include nums[i]
        path.append(nums[i])
        backtrack(i + 1)
        path.pop()                    # unchoose
        # choice 2: exclude nums[i]
        backtrack(i + 1)

    backtrack(0)
    return res

Worked trace. nums = [1, 2, 3]. Each line is one recursive call; indentation = depth. +x means “included x”; -x means “skipped x”.

backtrack(0)
├── +1 → backtrack(1)               path=[1]
│   ├── +2 → backtrack(2)           path=[1,2]
│   │   ├── +3 → backtrack(3)       path=[1,2,3]   → emit [1,2,3]
│   │   └── -3 → backtrack(3)       path=[1,2]     → emit [1,2]
│   └── -2 → backtrack(2)           path=[1]
│       ├── +3 → backtrack(3)       path=[1,3]     → emit [1,3]
│       └── -3 → backtrack(3)       path=[1]       → emit [1]
└── -1 → backtrack(1)               path=[]
    ├── +2 → backtrack(2)           path=[2]
    │   ├── +3 → backtrack(3)       path=[2,3]     → emit [2,3]
    │   └── -3 → backtrack(3)       path=[2]       → emit [2]
    └── -2 → backtrack(2)           path=[]
        ├── +3 → backtrack(3)       path=[3]       → emit [3]
        └── -3 → backtrack(3)       path=[]        → emit []

Eight leaves, eight subsets — 2³. Notice path is a single list mutated in place; path.copy() at the leaf is what makes each emitted result independent.

Flavor 2 — permutations (LC 46)

Permutations are an n-ary tree: at depth d, you pick any of the n - d remaining elements. Track which indices are taken with a used set so the membership check is O(1).

def permute(nums: list[int]) -> list[list[int]]:
    res, path = [], []
    used = [False] * len(nums)

    def backtrack() -> None:
        if len(path) == len(nums):
            res.append(path.copy())
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()                # unchoose value
            used[i] = False           # unchoose flag

    backtrack()
    return res

Brief trace. nums = [1, 2, 3]. Top-level branches:

backtrack()                   path=[],     used=[F,F,F]
├── pick 1 → path=[1]
│   ├── pick 2 → path=[1,2]
│   │   └── pick 3 → emit [1,2,3]
│   └── pick 3 → path=[1,3]
│       └── pick 2 → emit [1,3,2]
├── pick 2 → path=[2]   ...   → emit [2,1,3], [2,3,1]
└── pick 3 → path=[3]   ...   → emit [3,1,2], [3,2,1]

Six leaves, 3! = 6 permutations. The in-place swap variant avoids the used array entirely — swap nums[d] with nums[i], recurse, swap back — but the used version is easier to extend to “permutations with duplicates” (LC 47), which is why it’s the more common template.

Flavor 3 — N-queens (LC 51)

Place n queens on an n×n board so no two attack each other. Place one queen per row; track attacked columns and diagonals with three sets so each attack check is O(1).

Key observation: for any square (r, c), every cell on the same ↘ diagonal has the same value of r - c, and every cell on the same ↙ diagonal has the same value of r + c. That’s how three sets cover all attacks.

def solve_n_queens(n: int) -> list[list[str]]:
    res = []
    cols, diag, anti = set(), set(), set()   # attacked: col, r-c, r+c
    placement = [-1] * n                     # placement[r] = column

    def backtrack(r: int) -> None:
        if r == n:
            board = [
                "." * placement[i] + "Q" + "." * (n - 1 - placement[i])
                for i in range(n)
            ]
            res.append(board)
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue   # pruned: this square is attacked
            cols.add(c); diag.add(r - c); anti.add(r + c)
            placement[r] = c
            backtrack(r + 1)
            cols.remove(c); diag.remove(r - c); anti.remove(r + c)

    backtrack(0)
    return res

Trace one branch for n=4. Coordinates are (row, col), 0-indexed.

r=0, try c=0  → place (0,0)            cols={0}, diag={0}, anti={0}
  r=1, try c=0  → blocked (col)
       try c=1  → blocked (diag, 1-1=0)
       try c=2  → place (1,2)          cols={0,2}, diag={0,-1}, anti={0,3}
         r=2, try c=0  → blocked (col)
              try c=1  → blocked (anti, 2+1=3)
              try c=2  → blocked (col)
              try c=3  → blocked (diag, 2-3=-1)
              all blocked → return, unchoose (1,2)
       try c=3  → place (1,3)          cols={0,3}, diag={0,-2}, anti={0,4}
         r=2, try c=0  → blocked (col)
              try c=1  → place (2,1)   cols={0,1,3}, diag={0,-2,1}, anti={0,4,3}
                r=3, try c=0..3 all blocked → unchoose
              try c=2..3 blocked → unchoose (1,3)
       all of row 1 exhausted → unchoose (0,0)
r=0, try c=1 → place (0,1) → eventually finds solution [(0,1),(1,3),(2,0),(3,2)]

The pruning is doing real work: of the 4⁴ = 256 raw (c₀,c₁,c₂,c₃) tuples, the search visits a small fraction before finding the two valid solutions for n=4.

Why it works — the invariant

At every recursion level, the partial solution path is consistent with all constraints checked so far. The recursive call assumes that invariant and extends path by one more decision; the base case fires when path is a complete, valid solution and emits a copy.

The unchoose step is what makes this safe across siblings. Concretely: before the recursive call, the parent’s state is S. The recursive call mutates state, possibly emits results, and returns. The unchoose step restores state to exactly S, so the next sibling sees the same parent state the previous sibling saw. Without it, the second sibling inherits pollution from the first and you get garbage answers.

That’s the whole correctness story: invariant on the way down, exact restoration on the way up.

Complexity

• Time: O(branching^depth) at the worst case — 2ⁿ for subsets, n! for permutations, roughly n! for N-queens before pruning. Pruning drops the constant and shrinks the effective tree, often by orders of magnitude (N-queens with the three-set check goes from n! to something closer to n!/cⁿ empirically).
• Space: O(depth) for the recursion stack plus O(depth) for path; output space is separate and equal to the number of solutions emitted times their size.

Common pitfalls

• Forgetting to deep-copy path at the leaf. Appending path directly means every entry in res points at the same list, and after the run every result equals whatever path ended up as (usually []). Always path.copy() or path[:] before appending.
• Missing the unchoose step. State leaks from one branch to its sibling, and your “permutations” function emits sequences with repeats. Every append/add needs a matching pop/remove after the recursive call returns.
• O(n) in path membership checks. Doing if x in path on a list inside the inner loop turns each constraint check into O(n), which on top of the exponential tree is brutal. Use a set (or a boolean array) and you’re back to O(1) per check.
• Applying backtracking to a DP problem. “Number of ways to make change”, “longest common subsequence”, “edit distance” — these have overlapping subproblems. Pure backtracking re-explores the same partial state through different choice sequences and runs in exponential time when DP would do it in polynomial. If you can describe the state as a small tuple and notice the same tuple coming up from multiple paths, memoise.
• Pruning too late. Checking validity only at the leaf turns a constraint problem back into brute force. Push checks as high in the tree as you can — that’s the entire point of the pattern.

Where you see this in production

• SAT solvers (MiniSAT, Z3). Modern CDCL SAT solvers are backtracking search with heavy pruning: pick a variable, assign true, propagate unit clauses, recurse; on conflict, learn a clause and backtrack. Z3’s core is the same skeleton wrapped in conflict-driven clause learning.
• Regex engines that backtrack (Python re, Perl, Java Pattern). When the engine hits an alternation or a quantifier, it picks one branch, recurses on the rest of the input, and on failure backtracks to the next alternative. This is why catastrophic backtracking on patterns like (a+)+b happens — the choice tree explodes when the input doesn’t match.
• Prolog query resolution. Prolog’s entire execution model is backtracking SLD-resolution: try a clause, bind variables, recurse on subgoals, undo bindings on failure, try the next clause.
• Sudoku solvers. The textbook implementation is exactly this template: pick the most-constrained empty cell, try each legal digit, recurse, undo on failure. Newspaper apps and the OpenCV-tutorial-style solvers all use it.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.
• Abdul Bari — Backtracking lectures — www.youtube.com