15 — Backtracking

Some problems have no shortcut. The answer is one of a huge but structured set of candidates (every subset, every ordering, every placement of pieces on a board) and the only general method is to look through them. Backtracking is the disciplined way to do that: build a candidate one decision at a time, and the moment a partial candidate cannot possibly be completed into a valid answer, abandon it and undo the last decision. The work saved by abandoning early is the whole point. A brute-force enumeration of the 40,320 orderings of 8 queens checks every one; a backtracking search for the same answers visits 2,057 partial placements.

This chapter covers the template and the tree it explores, the three enumeration families (subsets, permutations, combinations) with and without duplicates, the classic constraint problems (N-Queens, Sudoku, Word Search, palindrome partitioning, Knight’s Tour, Rat in a Maze, phone letter combinations, balanced parentheses), and three techniques that sit next to backtracking: branch and bound, meet in the middle, and estimating how large a search will be before running it.

Every implementation below was checked against a brute-force reference (usually itertools) on hundreds of random inputs before being included. Timings were measured with Python 3.14 on one Mac using time.perf_counter, taking the best of several runs where a run was short enough to repeat. Exact numbers will differ elsewhere; node counts are machine-independent, and the ratios are the point.

The state-space tree

Every backtracking algorithm explores an implicit tree:

• The root is the empty partial solution: no decisions made.
• Each edge is one decision: include this element, place a queen in this column, write this digit in this cell.
• Each node is the partial solution reached by the decisions on the path from the root.
• Leaves are either complete solutions or dead ends, where no decision is legal.

The tree is never built in memory. Depth-first search walks it, holding only the current root-to-node path, so memory is proportional to the depth, not the size of the tree. That is the first reason backtracking is depth-first rather than breadth-first: breadth-first search over a tree with $10^8$ nodes would need to store a whole level at once, and the levels near the bottom are almost the whole tree.

For four queens on a 4×4 board, one queen per row, the full search looks like this (columns numbered 0 to 3, produced by instrumenting the solver below):

row 0 col 0: place
  row 1 col 0: attacked
  row 1 col 1: attacked
  row 1 col 2: place
    row 2 col 0: attacked
    row 2 col 1: attacked
    row 2 col 2: attacked
    row 2 col 3: attacked          <- dead end: undo row 1, try the next column
  row 1 col 3: place
    row 2 col 0: attacked
    row 2 col 1: place
      row 3 col 0: attacked
      row 3 col 1: attacked
      row 3 col 2: attacked
      row 3 col 3: attacked        <- dead end two levels deep
    row 2 col 2: attacked
    row 2 col 3: attacked
row 0 col 1: place
  row 1 col 0: attacked
  row 1 col 1: attacked
  row 1 col 2: attacked
  row 1 col 3: place
    row 2 col 0: place
      row 3 col 0: attacked
      row 3 col 1: attacked
      row 3 col 2: place
        solution [1, 3, 0, 2]
      ...

The whole trace is 62 lines for a problem whose unpruned tree (any column in any row) has $4^4 = 256$ leaves. Every “attacked” line is a subtree that was never entered.

The template: choose, explore, unchoose

Nearly every backtracking function has the same three-step body:

def backtrack(state):
    if is_complete(state):
        record(state)
        return
    for choice in candidates(state):
        if not is_valid(state, choice):
            continue                 # prune: this subtree holds no solution
        apply(state, choice)         # choose
        backtrack(state)             # explore
        undo(state, choice)          # unchoose

The invariant that makes this correct: when backtrack(state) returns, state is exactly what it was when the call began. Each apply is paired with an undo, so the caller can try its next choice from a clean state. Most backtracking bugs are violations of this invariant: a return in the middle of the loop that skips the undo, an undo that does not exactly reverse the apply, or a recorded solution that is a reference to the mutable state instead of a copy (out.append(path) instead of out.append(path[:]), which leaves out holding many references to one list that ends up empty).

There are two ways to keep the invariant:

Pruning

The size of the search is the size of the tree that is actually visited, and that is controlled entirely by how early invalid partial solutions are recognized. Three kinds of pruning show up repeatedly:

• Feasibility pruning. A partial solution already breaks a constraint (two queens attack each other; a running sum exceeds the target). Check constraints incrementally, as each choice is made, never only at the leaves.
• Symmetry and duplicate pruning. Two branches lead to identical results (choosing the first or the second of two equal values). Skip all but one.
• Bound pruning. In optimization, the best value any completion of this partial solution could possibly reach is no better than the best complete solution already found. This is branch and bound, covered later in the chapter.

A further lever is choice ordering: which variable to decide next and which value to try first. It does not change the set of solutions, but it can change the size of the visited tree by orders of magnitude, as the Sudoku and Knight’s Tour measurements show.

Complexity in general

The running time of a backtracking search is (number of nodes visited) × (work per node). The worst case is usually the size of the unpruned tree: $2^n$ leaves for subsets, $n!$ for permutations, $9^{k}$ for $k$ empty Sudoku cells. Pruning rarely improves the worst-case bound, which is why these problems are still described as exponential, but it routinely cuts the visited tree by factors of thousands on real inputs. Space is O(depth) for the recursion and the path, plus whatever the output takes.

Python’s default recursion limit is 1,000 frames. Search depths in this chapter are small (at most the number of squares on a board), but a backtracking search over a 50×50 Knight’s Tour is 2,500 levels deep and needs sys.setrecursionlimit raised, or an explicit stack.

Subsets

Problem. Given $n$ distinct values, list all $2^n$ subsets (the power set).

Each element gets one binary decision: leave it out or take it. The state-space tree is a complete binary tree of depth $n$ whose leaves are the subsets.

def subsets(nums):
    out, path = [], []
    def go(i):
        if i == len(nums):
            out.append(path[:])
            return
        go(i + 1)              # exclude nums[i]
        path.append(nums[i])   # choose
        go(i + 1)              # explore
        path.pop()             # unchoose
    go(0)
    return out

print(subsets([1, 2, 3]))

[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

There is a second, equally common shape: every node of the tree is a subset (not only leaves), and the loop picks the next element to add from those after the last one chosen. It records path on entry and loops for i in range(start, n). Both produce the same $2^n$ subsets in a different order. The second shape is the one that extends naturally to duplicates and to combinations.

Complexity. $2^n$ subsets with average size $n/2$, and each is copied once: $\Theta(n \cdot 2^n)$ time, O(n) extra space beyond the output. No algorithm can do better than the output size, so this is optimal. For $n \le 20$ or so, iterating over bitmasks for mask in range(1 << n) is an equivalent non-recursive alternative (chapter 17 covers subset enumeration by bitmask).

Subsets with duplicates

Problem. The input may contain repeated values; list each distinct subset once. For [1, 2, 2], [1, 2] should appear once even though there are two 2s to choose from.

Sort the input so equal values are adjacent. Then, at any one level of the tree, try each distinct value only once: if nums[i] == nums[i - 1] and i > start, skip it. The condition i > start is the important part. It allows [2, 2] (the second 2 chosen at a deeper level, where i == start), while forbidding a second branch that starts with “the other 2” at the same level, which would produce exactly the subtree the first 2 already produced.

def subsets_with_dup(nums):
    nums = sorted(nums)
    out, path = [], []
    def go(start):
        out.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue       # same value already tried at this depth
            path.append(nums[i])
            go(i + 1)
            path.pop()
    go(0)
    return out

print(subsets_with_dup([1, 2, 2]))

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

Deduplicating afterwards with a set of tuples also gives the right answer, but it still explores every duplicate branch; with many repeated values the duplicate subtrees dominate the work. The skip rule never generates them.

Permutations

Problem. List all $n!$ orderings of $n$ distinct values.

At depth $d$ the path holds $d$ chosen values and any of the $n - d$ unused ones may come next, so the tree has branching factor $n, n-1, \ldots, 1$. A boolean used array marks what is already in the path.

def permutations(nums):
    out, path = [], []
    used = [False] * len(nums)
    def go():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            go()
            path.pop()
            used[i] = False
    go()
    return out

An alternative avoids the used array by swapping: at depth $d$, swap each of positions $d..n-1$ into position $d$, recurse, and swap back. It uses no extra array but does not produce lexicographic order, and its duplicate handling is less obvious.

Complexity. $n!$ leaves, each copied in O(n): $\Theta(n \cdot n!)$ time. The internal nodes add $n!\,(1/1! + 1/2! + \cdots)$, which is less than $e \cdot n!$, so they do not change the bound. Factorial growth is the steepest in this chapter: 10! is 3.6 million, 12! is 479 million. Problems that ask for “the best ordering” over more than about 11 items need dynamic programming over subsets (chapter 14, and the Traveling Salesman section of chapter 13), not enumeration.

Permutations with duplicates

For [1, 1, 2] there are $3!/2! = 3$ distinct orderings, not 6. Sort the input and add one rule: a duplicate may be used only if its identical left neighbor is already in the path. That forces equal values to be placed in their original left-to-right order, so each distinct arrangement is built exactly once.

def permutations_unique(nums):
    nums = sorted(nums)
    out, path = [], []
    used = [False] * len(nums)
    def go():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            go()
            path.pop()
            used[i] = False
    go()
    return out

print(permutations_unique([1, 1, 2]))

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

The condition not used[i - 1] is sometimes written as used[i - 1]; that variant also produces each permutation once (it forces equal values into right-to-left order instead), but it prunes much later in the tree. Counting nodes visited on [1, 1, 1, 1, 1, 2, 2, 2, 2, 2] (252 distinct permutations): 923 with not used[i - 1], 91,177 with used[i - 1]. On [1, 1, 2, 2, 3, 3, 4, 4] the counts are 7,365 and 16,201.

Combinations

Problem. List all $k$-element subsets of $\{1, \ldots, n\}$, of which there are $\binom{n}{k}$.

This is the “every node is a subset” shape stopped at depth $k$. Choosing values in increasing order makes each combination appear once. One extra prune matters: if fewer values remain than slots to fill, the branch cannot finish, so the loop’s upper limit is tightened to leave room.

def combine(n, k):
    out, path = [], []
    def go(start):
        if len(path) == k:
            out.append(path[:])
            return
        # need k - len(path) more numbers from start..n
        for x in range(start, n - (k - len(path)) + 2):
            path.append(x)
            go(x + 1)
            path.pop()
    go(1)
    return out

print(combine(4, 2))

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

With the tightened limit, every internal node visited has at least one leaf below it, so the time is $\Theta(k \binom{n}{k})$ with no wasted branches.

Combination Sum, three variants

The “Combination Sum” family asks for multisets of candidates that add to a target. The variants differ only in two lines of the same template:

Passing i instead of i + 1 is what allows the same candidate to be chosen again at the next depth. Sorting the candidates enables an early break: once one candidate exceeds the remaining amount, every later one does too.

def combination_sum(candidates, target):
    """Each candidate may be reused any number of times (distinct candidates)."""
    cands = sorted(candidates)
    out, path = [], []
    def go(start, remaining):
        if remaining == 0:
            out.append(path[:])
            return
        for i in range(start, len(cands)):
            if cands[i] > remaining:
                break          # sorted, so every later candidate is too big
            path.append(cands[i])
            go(i, remaining - cands[i])   # i, not i + 1: reuse allowed
            path.pop()
    go(0, target)
    return out


def combination_sum2(candidates, target):
    """Each candidate used at most once; candidates may contain duplicates."""
    cands = sorted(candidates)
    out, path = [], []
    def go(start, remaining):
        if remaining == 0:
            out.append(path[:])
            return
        for i in range(start, len(cands)):
            if i > start and cands[i] == cands[i - 1]:
                continue
            if cands[i] > remaining:
                break
            path.append(cands[i])
            go(i + 1, remaining - cands[i])
            path.pop()
    go(0, target)
    return out

print(combination_sum([2, 3, 6, 7], 7))
print(combination_sum2([10, 1, 2, 7, 6, 1, 5], 8))

[[2, 2, 3], [7]]
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

Combination Sum III (choose exactly $k$ distinct digits from 1 to 9 summing to $n$) uses the combine shape with the sum check added; its search space is at most $2^9 = 512$ subsets.

Pitfalls. The break is only valid when all candidates are positive. With zero or negative candidates, an unlimited-reuse search does not terminate (a zero can be added forever) and the early exit is wrong. If the question asks only for the number of combinations, or the minimum count, enumeration is the wrong tool; the counting version is the unbounded knapsack / coin change DP in chapter 14, which runs in O(n × target).

N-Queens

Problem. Place $n$ queens on an $n \times n$ board so that no two share a row, column or diagonal. Return all solutions, or count them.

The core idea

Because no two queens can share a row, there is exactly one queen per row, so the search decides one row at a time: in which column does the queen of row $r$ go? That alone shrinks the space from $\binom{n^2}{n}$ placements to $n^n$. Checking columns as they are used shrinks it to the $n!$ permutations, and checking diagonals during the search, rather than at the end, removes most of what remains.

Two squares $(r_1, c_1)$ and $(r_2, c_2)$ are on the same diagonal (running top-left to bottom-right) when $r_1 - c_1 = r_2 - c_2$ and on the same anti-diagonal (top-right to bottom-left) when $r_1 + c_1 = r_2 + c_2$. Keeping three sets (used columns, used $r - c$ values, used $r + c$ values) makes each safety check O(1).

def solve_n_queens(n):
    """Return every solution as a list of strings."""
    cols, diag, anti = set(), set(), set()
    placement = []            # placement[r] = column of the queen in row r
    out = []
    def go(r):
        if r == n:
            out.append(["." * c + "Q" + "." * (n - c - 1) for c in placement])
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue
            cols.add(c); diag.add(r - c); anti.add(r + c); placement.append(c)
            go(r + 1)
            cols.remove(c); diag.remove(r - c); anti.remove(r + c); placement.pop()
    go(0)
    return out

print("\n".join(solve_n_queens(4)[0]))

.Q..
...Q
Q...
..Q.

The bitmask version

The three sets can be replaced by three integers used as bit sets, one bit per column. The trick is to store the diagonals relative to the current row: a queen in column $c$ attacks column $c + 1$ one row down on one diagonal and $c - 1$ on the other. So moving to the next row is a shift: the diagonal mask shifts one way and the anti-diagonal mask the other. The free columns for the current row are then one expression, and free & -free isolates the lowest free column (two’s complement; see chapter 17).

def count_queens_bits(n):
    full = (1 << n) - 1
    def go(cols, d1, d2):
        if cols == full:
            return 1
        total = 0
        free = full & ~(cols | d1 | d2)
        while free:
            bit = free & -free          # lowest free column
            free ^= bit
            total += go(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
        return total
    return go(0, 0, 0)

There is no undo step: each recursive call receives new integers, and the caller’s integers are untouched. This is the “copy on descent” approach, made cheap because the whole state is three machine-sized values.

Measured

Solution counts and times for counting all solutions with the set version (a counting variant of the function above that does not build strings) and the bitmask version:

Three things to read from the table:

• The bitmask version is about 4× faster in Python, and it visits exactly the same nodes. The gain is all per-node cost: integer operations instead of hashing into three sets and mutating them twice. In a compiled language the gap is larger, because the bitmask version compiles to a handful of register instructions.
• Both grow roughly 5× per extra row in this range. Pruning does not change the exponential nature of the problem; it changes the base.
• Pruning is what matters most. Generating all 40,320 permutations of 8 columns and checking diagonals afterwards (rows and columns are automatically distinct in a permutation) took 15.8 ms for $n = 8$, against 1.19 ms for the pruned set version and 0.26 ms for the bitmask one. At $n = 12$ the unpruned approach would examine 479 million permutations.

The solution count for $n = 6$ (4) is smaller than for $n = 5$ (10); the sequence is not monotone at the start. There is no known closed formula for the number of solutions. For a single solution, constructive formulas exist that place queens in O(n) for every $n \ge 4$, so searching for one solution on a large board is the wrong approach.

Sudoku

Problem. Fill a 9×9 grid so that each row, column and 3×3 box contains the digits 1 to 9 once, consistent with the given clues.

Plain backtracking

Walk the empty cells in reading order and try each digit that does not already appear in the cell’s row, column or box. Three arrays of 9-bit masks (rows[r], cols[c], boxes[b], bit $v$ set when digit $v$ is used) make the legality test one OR and one AND.

That search is correct, but its order is fixed in advance, so it may spend a long time filling cells that are unconstrained while a cell further down has already been squeezed to zero legal digits. Two ideas fix that.

Minimum remaining values

Minimum remaining values (MRV), also called “most constrained variable first” or “fail first”, picks the empty cell with the fewest legal digits as the next one to branch on. A cell with one legal digit is a forced move and costs no branching at all. A cell with zero legal digits is a dead end discovered immediately, instead of after filling every cell before it in reading order.

ALL = 0x3FE  # bits 1..9


def box(r, c):
    return (r // 3) * 3 + c // 3


def masks(grid):
    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
    for r in range(9):
        for c in range(9):
            v = grid[r][c]
            if v:
                bit = 1 << v
                rows[r] |= bit; cols[c] |= bit; boxes[box(r, c)] |= bit
    return rows, cols, boxes


def solve_mrv(grid):
    """Always branch on the empty cell with the fewest legal digits."""
    rows, cols, boxes = masks(grid)
    empties = {(r, c) for r in range(9) for c in range(9) if grid[r][c] == 0}
    def go():
        if not empties:
            return True
        best, best_free, best_n = None, 0, 10
        for (r, c) in empties:
            free = ALL & ~(rows[r] | cols[c] | boxes[box(r, c)])
            n = free.bit_count()
            if n < best_n:
                best, best_free, best_n = (r, c), free, n
                if n <= 1:
                    break
        if best_n == 0:
            return False                      # dead end detected early
        r, c = best
        b = box(r, c)
        empties.remove(best)
        free = best_free
        while free:
            bit = free & -free
            free ^= bit
            grid[r][c] = bit.bit_length() - 1
            rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit
            if go():
                return True
            rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit
        grid[r][c] = 0
        empties.add(best)
        return False
    return go()

Scanning all empty cells to find the minimum costs up to 81 mask computations per node, which is far more per-node work than plain backtracking. It pays because it cuts the number of nodes much more than it raises their cost.

Constraint propagation

Constraint propagation goes further: keep a candidate set for every cell, and whenever a digit is fixed, remove it from all 20 peers (the other cells in its row, column and box), and keep applying two deduction rules until nothing changes:

• Naked single. A cell with one candidate left must take it, which removes that digit from its peers in turn.
• Hidden single. If a digit fits in only one cell of some row, column or box, it must go there.

If any cell’s candidates become empty, or any digit has no place in some unit, the current branch is contradictory. The search only branches (choosing the cell with fewest candidates, as in MRV) when propagation stalls. Undoing a cascade of eliminations is awkward, so this solver copies the 81-entry candidate list at each branch instead of undoing. This design is the one Peter Norvig popularized in his widely read Sudoku essay.

UNITS = ([[r * 9 + c for c in range(9)] for r in range(9)] +
         [[r * 9 + c for r in range(9)] for c in range(9)] +
         [[(br + i) * 9 + bc + j for i in range(3) for j in range(3)]
          for br in (0, 3, 6) for bc in (0, 3, 6)])
CELL_UNITS = [[u for u in UNITS if i in u] for i in range(81)]
PEERS = [sorted({j for u in CELL_UNITS[i] for j in u if j != i}) for i in range(81)]


def assign(cand, i, bit):
    """Set cell i to digit-bit; propagate. Return False on contradiction."""
    others = cand[i] & ~bit
    while others:
        b = others & -others
        others ^= b
        if not eliminate(cand, i, b):
            return False
    return True


def eliminate(cand, i, bit):
    if not cand[i] & bit:
        return True
    cand[i] &= ~bit
    if cand[i] == 0:
        return False                          # no digit left for this cell
    if cand[i] & (cand[i] - 1) == 0:          # naked single: one digit left
        for p in PEERS[i]:
            if not eliminate(cand, p, cand[i]):
                return False
    for u in CELL_UNITS[i]:                   # hidden single: digit fits one place
        places = [j for j in u if cand[j] & bit]
        if not places:
            return False
        if len(places) == 1 and cand[places[0]] != bit:
            if not assign(cand, places[0], bit):
                return False
    return True


def solve_propagate(grid):
    cand = [ALL] * 81
    for r in range(9):
        for c in range(9):
            if grid[r][c] and not assign(cand, r * 9 + c, 1 << grid[r][c]):
                return False
    def go(cand):
        best, best_n = -1, 10
        for i in range(81):
            n = cand[i].bit_count()
            if 1 < n < best_n:
                best, best_n = i, n
        if best == -1:
            return cand                       # every cell has one digit
        free = cand[best]
        while free:
            bit = free & -free
            free ^= bit
            trial = cand[:]                   # copy instead of undo
            if assign(trial, best, bit):
                res = go(trial)
                if res:
                    return res
        return None
    res = go(cand)
    if not res:
        return False
    for i in range(81):
        grid[i // 9][i % 9] = res[i].bit_length() - 1
    return True

Measured

Three puzzles: a commonly reproduced newspaper-style example; a puzzle published by Arto Inkala in 2012 and widely reported as “the world’s hardest Sudoku”; and a 17-clue puzzle constructed so that its first row’s solution is 9 8 7 6 5 4 3 2 1, which forces a reading-order search that tries digits upward to fail on almost every early choice. “Placements” counts digits written into the grid during search (for the propagating solver, branch decisions; its forced deductions are not counted).

The newspaper puzzle is solved by propagation alone (zero branches), so its 0.6 ms is pure set-up and deduction cost, more than MRV’s 0.1 ms on the same puzzle; for inputs this constrained, the cleverer solver loses on constant factors. On harder inputs, the node counts fall by one to two orders of magnitude with each idea. The anti-brute-force puzzle shows that a fixed variable order is not just slower but fragile: 69 million placements and almost a minute, against under 4,000 placements for MRV. An adversary who knows the order can construct an input that defeats it; MRV and propagation choose their order from the puzzle itself.

Generalized $n^2 \times n^2$ Sudoku is NP-complete, so no solver avoids exponential worst cases in general. For the 9×9 case, constraint propagation plus MRV solves essentially every published puzzle in milliseconds. Dancing Links (Knuth’s Algorithm X with a doubly linked sparse matrix) is the other standard approach, treating Sudoku as an exact cover problem.

Word Search

Problem. Given a grid of letters and a word, decide whether the word can be traced through horizontally or vertically adjacent cells, using each cell at most once.

Start a depth-first search from every cell. At step $i$ the current cell must match word[i]; then try the four neighbors for word[i + 1]. The “each cell at most once” rule is the backtracking part: mark the cell as used before exploring and unmark it afterwards, because it may legitimately be used by a different path later. Overwriting the cell with a sentinel and restoring it avoids a separate visited structure.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def go(r, c, i):
        if board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        saved, board[r][c] = board[r][c], "#"      # mark as used on this path
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and go(nr, nc, i + 1):
                board[r][c] = saved
                return True
        board[r][c] = saved                          # unchoose
        return False
    return any(go(r, c, 0) for r in range(rows) for c in range(cols))

board = [list("ABCE"), list("SFCS"), list("ADEE")]
print(exist(board, "ABCCED"), exist(board, "SEE"), exist(board, "ABCB"))

True True False

Note the restore on the success path: without it, a True return leaves # characters in the caller’s board. The test harness for this function checks that the board is unchanged after every call.

Complexity. From each of the $R \cdot C$ starting cells, the first step has up to 4 directions and later steps at most 3 (the cell just came from is marked), so the time is $O(R \cdot C \cdot 3^{L})$ for a word of length $L$, space O(L) for the recursion. Useful prunes on real inputs: return False immediately if the board does not contain enough of each letter of the word (a Counter comparison), and if the last letter of the word is rarer on the board than the first, search for the reversed word instead, so the search starts from fewer cells.

Word Search II (find all of many words in one grid) should not run this search once per word. Build a trie of the words and do one DFS from each cell that walks the trie alongside the grid, abandoning a path as soon as the prefix is not in the trie. Tries are in chapter 11.

Palindrome partitioning

Problem. Split a string into pieces that are all palindromes; return every such split.

The decisions are where to cut. From position start, any end position whose substring s[start..end] is a palindrome is a legal next piece. Checking palindromes repeatedly is wasteful, so a quadratic table pal[i][j] is computed first (a small DP: s[i..j] is a palindrome when the end characters match and s[i+1..j-1] is one).

def partition(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] is a palindrome
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    out, path = [], []
    def go(start):
        if start == n:
            out.append(path[:])
            return
        for end in range(start, n):
            if pal[start][end]:
                path.append(s[start:end + 1])
                go(end + 1)
                path.pop()
    go(0)
    return out

print(partition("aab"))
print(len(partition("aaaaaaaaaa")), len(partition("abcdefghij")))

[['a', 'a', 'b'], ['aa', 'b']]
512 1

The output size is the complexity driver. A string of $n$ identical characters has every one of its $2^{n-1}$ cut sets valid (512 for ten characters), so the worst case is $O(n \cdot 2^n)$ time; a string with all distinct characters has exactly one partition. If the question is the minimum number of cuts (Palindrome Partitioning II), enumerating is the wrong approach: that is an $O(n^2)$ DP using the same pal table.

Knight’s Tour

Problem. Move a chess knight so that it visits every square of an $n \times n$ board exactly once. (A closed tour also ends one knight’s move from its start; the version here is open.)

This is a Hamiltonian path problem on the knight’s-move graph (chapter 13 covers Hamiltonian paths in general). Plain backtracking tries the eight moves in a fixed order. Warnsdorff’s rule, published by H. C. von Warnsdorff in 1823, changes only the order: move to the square that has the fewest onward moves still available. It is the MRV heuristic again. Squares near corners and edges have few exits, and the rule visits them while they still can be reached, instead of stranding them.

MOVES = ((2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1))


def knights_tour(n, warnsdorff, start=(0, 0)):
    board = [[-1] * n for _ in range(n)]

    def inside_free(r, c):
        return 0 <= r < n and 0 <= c < n and board[r][c] == -1

    def degree(r, c):
        return sum(inside_free(r + dr, c + dc) for dr, dc in MOVES)

    def go(r, c, step):
        board[r][c] = step
        if step == n * n - 1:
            return True
        nxt = [(r + dr, c + dc) for dr, dc in MOVES if inside_free(r + dr, c + dc)]
        if warnsdorff:
            nxt.sort(key=lambda p: degree(*p))   # fewest onward moves first
        for nr, nc in nxt:
            if go(nr, nc, step + 1):
                return True
        board[r][c] = -1                         # unchoose
        return False

    return board if go(*start, 0) else None

Measured from the corner square, with the same code and only the ordering flag changed (“nodes” counts squares the knight stepped onto, including those later undone):

With Warnsdorff ordering the number of nodes equals the number of squares on every board tested: from the corner, the search never backtracked once. The plain search’s cost depends on the starting square in ways that are hard to predict. On 6×6, starting from the corner took 248,169 nodes, while starting from (0, 1), (1, 2) and (2, 2) took 2.6 million, 2.8 million and 2.4 million. On 5×5, starting from (0, 1) explored 1,829,421 nodes before proving that no tour exists from that square (on boards with an odd number of squares, an open tour must start on the color that has more squares).

Warnsdorff’s rule is a heuristic, not a guarantee. Run as a pure greedy walk with no backtracking (ties broken by the order of MOVES), it got stuck from 1 of the 64 starting squares on 8×8, 2 of 100 on 10×10, 5 of 400 on 20×20 and 310 of 2,500 on 50×50. That is why the implementation keeps the backtracking loop behind it: the heuristic decides the order, the backtracking guarantees completeness. On very large boards, divide-and-conquer constructions that stitch together small precomputed tours are used instead.

Rat in a Maze

Problem. In an $n \times n$ grid of open (1) and blocked (0) cells, list every path from the top-left to the bottom-right corner that moves up, down, left or right and does not revisit a cell. Paths are reported as strings of the letters D, L, R, U, conventionally in lexicographic order.

The structure is Word Search without a word: mark the cell, try the four directions, unmark. Trying the moves in the order D, L, R, U produces the paths already sorted.

def rat_in_maze(maze):
    """All paths from (0,0) to (n-1,n-1) moving D, L, R, U through 1-cells."""
    n = len(maze)
    if not maze[0][0] or not maze[n - 1][n - 1]:
        return []
    moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
    seen = [[False] * n for _ in range(n)]
    out, path = [], []
    def go(r, c):
        if (r, c) == (n - 1, n - 1):
            out.append("".join(path))
            return
        seen[r][c] = True
        for name, dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] and not seen[nr][nc]:
                path.append(name)
                go(nr, nc)
                path.pop()
        seen[r][c] = False
    go(0, 0)
    return out

maze = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]
print(rat_in_maze(maze))

['DDRDRR', 'DRDDRR']

The number of simple paths in a grid grows exponentially with $n$, so listing them all is exponential in the worst case. If the question is only whether a path exists, or the shortest path, use BFS (chapter 12) in O(n²): no unmarking, because a cell that was reached once never needs to be reached again. The difference between “mark permanently” (graph search) and “mark, then unmark” (enumerating paths) is exactly the difference between polynomial and exponential.

Letter Combinations of a Phone Number

Problem. Each digit 2 to 9 maps to three or four letters on a phone keypad; list every string a digit sequence can spell.

Every combination of choices is valid, so there is nothing to prune; the backtracking is a Cartesian product written as recursion.

KEYS = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letter_combinations(digits):
    if not digits:
        return []
    out, path = [], []
    def go(i):
        if i == len(digits):
            out.append("".join(path))
            return
        for ch in KEYS[digits[i]]:
            path.append(ch)
            go(i + 1)
            path.pop()
    go(0)
    return out

print(letter_combinations("23"))

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

The output has up to $4^n$ strings of length $n$, so time is $O(n \cdot 4^n)$. In Python, itertools.product(*(KEYS[d] for d in digits)) gives the same strings in the same order, and the test harness checks against it. The empty input returns [] by the usual problem convention, even though the product of zero sets is mathematically one empty string; that edge case is worth checking against whatever specification applies.

Generate Parentheses

Problem. List every balanced string of $n$ pairs of parentheses.

A prefix can be extended to a balanced string if and only if it never has more ) than ( and has at most $n$ of (. So the search adds ( while fewer than $n$ are open, and adds ) only while it would not close more than were opened. Every leaf the search reaches is then a valid answer: the pruning is exact, and no dead ends are ever entered.

def generate_parentheses(n):
    out, path = [], []
    def go(opened, closed):
        if len(path) == 2 * n:
            out.append("".join(path))
            return
        if opened < n:
            path.append("("); go(opened + 1, closed); path.pop()
        if closed < opened:
            path.append(")"); go(opened, closed + 1); path.pop()
    go(0, 0)
    return out

print(generate_parentheses(3))
print([len(generate_parentheses(n)) for n in range(1, 11)])

['((()))', '(()())', '(())()', '()(())', '()()()']
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]

Catalan numbers

The counts 1, 2, 5, 14, 42, … are the Catalan numbers:

$C_n = \frac{1}{n+1}\binom{2n}{n}, \qquad C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$

The harness confirmed the formula against the generated count for $n$ up to 7, and the list above matches it up to 10. The same numbers count many other structures, which is a useful recognition signal: binary trees with $n$ nodes (Unique Binary Search Trees), ways to triangulate a convex polygon with $n + 2$ sides, monotone lattice paths that do not cross the diagonal, and ways to fully parenthesize a product of $n + 1$ factors. They also satisfy the recurrence $C_0 = 1$, $C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}$, which splits a balanced string at the ) matching its first (.

Since all leaves are output, time is $\Theta(n \cdot C_n)$, which is roughly $4^n / \sqrt{n}$: smaller than the $4^n$ strings of length $2n$ by a polynomial factor only.

Branch and bound

Backtracking for optimization (find the best solution, not all of them) adds one more prune. Keep the best complete solution found so far, the incumbent. At each node, compute an optimistic bound: a value that no completion of this partial solution can beat. If the bound is no better than the incumbent, the subtree cannot contain an improvement, and is skipped.

The method’s correctness rests on one property: the bound must be optimistic (an upper bound when maximizing, a lower bound when minimizing). A bound that is sometimes too pessimistic prunes subtrees that contain the optimum, and the algorithm returns a wrong answer without any sign of it. Its speed rests on two others: the bound should be tight (close to the true best completion), and the incumbent should become good early, which is why branch and bound tries the most promising branch first. The method was introduced by Ailsa Land and Alison Doig in 1960 for integer programming.

0/1 knapsack with a fractional bound

Problem. Items have values $v_i$ and weights $w_i$; choose a subset with total weight at most $W$ and maximum total value. Each item is taken whole or not at all.

The bound comes from the fractional knapsack, where items may be split: sort items by value per unit weight, take them greedily in that order, and take a fraction of the first one that does not fit. That greedy is optimal for the fractional problem (proved in chapter 16), and every 0/1 solution is also a fractional solution, so the fractional optimum of the remaining items is a valid optimistic bound for the 0/1 problem.

def knapsack_bnb(items, cap):
    """Depth-first branch and bound with the fractional-knapsack bound."""
    items = sorted(items, key=lambda it: it[0] / it[1], reverse=True)
    n = len(items)
    best = 0

    def bound(i, value, room):
        # optimistic: fill greedily by ratio, taking a fraction of the first misfit
        for v, w in items[i:]:
            if w <= room:
                room -= w
                value += v
            else:
                return value + v * room / w
        return value

    def go(i, value, room):
        nonlocal best
        if value > best:
            best = value
        if i == n or bound(i, value, room) <= best:
            return                                    # cannot beat incumbent
        v, w = items[i]
        if w <= room:
            go(i + 1, value + v, room - w)            # include first: finds good incumbents early
        go(i + 1, value, room)

    go(0, 0, cap)
    return best

Items are visited in ratio order, so the bound for the remaining items is a prefix scan. The “include” branch is explored first, which makes the very first leaf reached equal to the greedy solution, usually a strong incumbent.

The comparison is with plain include/exclude backtracking that prunes only on capacity (an item is not taken if it does not fit). Both were checked against the O(nW) DP from chapter 14 on random inputs. Random instances have independent values and weights in 10 to 100 and a capacity of half the total weight:

Instances where each value is the weight plus 10 (“strongly correlated” instances, a standard hard family for knapsack solvers, because all items have similar ratios and the fractional bound is barely better than the incumbent):

The plain search grows by about 32× for five more items, which is the $2^n$ shape exactly. Branch and bound visits a few hundred nodes on random instances and some thousands on correlated ones, and its node count is not monotone in $n$: it depends on how quickly the bound and the incumbent meet, which is a property of the particular instance rather than its size. The worst case of branch and bound is still exponential; adversarial knapsack instances exist that defeat this bound. For integer weights with a modest capacity, the O(nW) DP has a guaranteed bound, and for large or real-valued weights, branch and bound is what practical solvers use.

Best-first versus depth-first

The version above is depth-first: memory is O(n) and a feasible incumbent appears immediately. Best-first branch and bound keeps the open nodes in a priority queue ordered by bound and always expands the most promising one. It expands the fewest nodes of any strategy using the same bound (it never expands a node whose bound is below the optimum), but the queue can grow exponentially, and it may not have a complete solution until late. Depth-first is the usual choice when memory matters or when a good answer is wanted early.

Meet in the middle

Problem. Given $n$ integers (positive, negative or zero) and a target, find the subset sum closest to the target. With $n = 40$, the $2^{40} \approx 1.1 \times 10^{12}$ subsets are out of reach, and there is no pruning rule that works for arbitrary signs.

The idea. Split the array into two halves of size $n/2$. Every subset of the whole array is a subset $L$ of the left half combined with a subset $R$ of the right half, and its sum is $\text{sum}(L) + \text{sum}(R)$. Enumerate the $2^{n/2}$ sums of each half separately, sort the right half’s sums, and for each left sum $s$ binary-search the right list for the value closest to $\text{target} - s$. The search space is still $2^n$ pairs, but sorting lets each left sum find its best partner in $O(\log 2^{n/2}) = O(n)$ steps instead of trying all $2^{n/2}$.

from bisect import bisect_left


def all_sums(nums):
    sums = [0]
    for x in nums:
        sums += [s + x for s in sums]     # doubles each step
    return sums


def closest_subset_sum_mitm(nums, goal):
    half = len(nums) // 2
    left = all_sums(nums[:half])
    right = sorted(all_sums(nums[half:]))
    best = abs(goal)
    for s in left:
        want = goal - s
        k = bisect_left(right, want)          # first right sum >= want
        if k < len(right):
            best = min(best, right[k] - want)
        if k > 0:
            best = min(best, want - right[k - 1])
    return best

The function returns the smallest distance $\lvert \text{sum} - \text{goal} \rvert$, including the empty subset (sum 0). Both candidates around the insertion point must be checked: the first right sum at or above want, and the last one below it.

Complexity. $O(2^{n/2} \cdot n)$ time (dominated by sorting $2^{n/2}$ sums and $2^{n/2}$ binary searches) and $O(2^{n/2})$ space. The technique trades exponential memory for a square-root reduction in time: $2^{40}$ becomes about $2^{20} \times 20$. The method was published by Ellis Horowitz and Sartaj Sahni in 1974 for subset sum and knapsack.

Measured against the brute force that builds all $2^n$ subset sums with the same doubling loop (random values up to $\pm 10^7$):

The speedup roughly doubles with every two extra elements, as $2^n / 2^{n/2} = 2^{n/2}$ predicts. Brute force at $n = 40$ would extrapolate to about 16 hours from the $n = 24$ row (multiplying by $2^{16}$), and would need terabytes of memory to hold the list of sums. Meet in the middle at $n = 40$ holds two lists of about a million sums each.

Where it applies. The pattern is: a search over $n$ independent choices whose objective decomposes as a combination of the two halves, with $n$ around 30 to 45 (too large for $2^n$, small enough for $2^{n/2}$ in memory). Classic uses are subset sum and its closest-sum and counting variants (Closest Subsequence Sum; Partition Array Into Two Arrays to Minimize Sum Difference, which groups half-sums by subset size), 4-Sum (pair sums from two halves of the four positions, $O(n^2)$ instead of $O(n^4)$), and bidirectional BFS (chapter 12), which is meet in the middle applied to a search graph.

Estimating the search tree before writing code

Backtracking costs are hard to guess. Before writing a full solver, two kinds of estimate help decide whether the approach is feasible at all.

Upper bounds from counting. The unpruned tree size is a product of branching factors: $2^n$, $n!$, $\binom{n}{k}$, $9^{\text{empty cells}}$. If that is under about $10^7$ in Python (see the operations-per-second calibration in chapter 18), any correct backtracking finishes and the effort should go to correctness, not pruning. If it is $10^{15}$, pruning has to remove almost all of it, and it is worth knowing in advance whether it will.

Knuth’s random-probe estimator. Donald Knuth showed in 1975 (“Estimating the efficiency of backtrack programs”) that a single random root-to-leaf walk gives an unbiased estimate of the size of a backtracking tree. Walk down from the root choosing a uniformly random child at each node, and record the number of children $d_0, d_1, d_2, \ldots$ seen at each level. The estimate is

$\hat{N} = 1 + d_0 + d_0 d_1 + d_0 d_1 d_2 + \cdots$

The intuition: if the walk reaches level $k$ by passing nodes with $d_0, \ldots, d_{k-1}$ children, then, if every node at those levels branched the same way, there would be $d_0 d_1 \cdots d_{k-1}$ nodes at level $k$. The tree is not that uniform, but the probability of reaching any particular node is exactly the reciprocal of that product along its path, which is what makes the average of many walks unbiased. Each walk costs only O(depth) node expansions.

def knuth_estimate(children, probes, rng):
    """children(path) returns the legal next choices after the partial solution path."""
    total = 0
    for _ in range(probes):
        path, weight, est = [], 1, 1
        while True:
            kids = children(path)
            if not kids:
                break
            weight *= len(kids)
            est += weight
            path.append(rng.choice(kids))
        total += est
    return total / probes

Applied to N-Queens, where children returns the safe columns for the next row (and nothing once $n$ queens are placed), with 1,000 probes each:

(The exact counts here use a slower, list-based safety check than the solvers above; the node counts are what matter.) For $n = 13$, a twentieth of a second of probing predicted the size of a 23-second search to within 1%. The method’s weakness is variance: when most of the tree hides in a few rare, deep branches, random walks rarely find them, and the estimate is usually too low with occasional huge overshoots. Running the estimator several times and comparing the results shows whether that is happening. The same estimator also compares two pruning rules or orderings before either full search is run.

Pitfalls across backtracking problems

The last row is the most important judgment call. Backtracking explores each partial solution separately even when two different paths lead to the same remaining subproblem. When that overlap exists and the remaining subproblem can be summarized by a small state (an index and a remaining sum, say), memoizing it turns the search into dynamic programming, and an exponential tree collapses into a polynomial table. When the state cannot be summarized (the set of used squares in a Knight’s Tour, the full board in Sudoku), backtracking with good pruning and ordering is what remains.

Summary