Backtracking

Backtracking is a depth-first search over partial solutions, and two things separate a usable implementation from a brute-force one: the undo that keeps sibling branches independent, and the pruning that removes whole subtrees before they are generated. This guide develops the choose-explore-unchoose shape, the difference between recording answers at leaves and at every node, and the constraint propagation and ordering heuristics that decide whether a search finishes in milliseconds or never. It also draws the boundaries: when overlapping subproblems mean the problem is really dynamic programming, when only a count is needed and enumeration is the wrong tool entirely, and why any search over untrusted input needs an explicit node budget.

backtracking as a search over a decision tree

Backtracking is a depth-first search over a tree of partial solutions, where each level fixes one decision.

The recursion extends a partial candidate, recurses, and then undoes the extension, so the same mutable state serves every branch.

One level per decision, and the undo is what makes siblings independent.

def search(state, depth):
    if complete(state): record(state); return
    for choice in options(state, depth):
        apply(state, choice)          # choose
        search(state, depth + 1)      # explore
        undo(state, choice)           # unchoose

Interview trap. Describing it as 'try everything' omits the pruning and the undo, which are the two parts that make it usable and correct.

Engineering practice. Name the decision each level makes, and write the undo immediately after the recursive call so the pairing cannot drift.

the choose-explore-unchoose shape

Every backtracking function has three parts in a fixed order: make the choice, recurse, undo the choice.

The undo restores the state exactly as it was, which is what makes sibling branches independent of exploration order.

Keep the undo adjacent to the change so the pairing cannot drift.

path.append(v)
search(...)
path.pop()          # directly after - not at the end of the function

Assert the state is unchanged after the call in tests: before = snapshot(state) ... assert snapshot(state) == before.

Interview trap. Omitting the undo leaks state between branches, producing results that change depending on the order in which options were tried.

Engineering practice. Keep the choice and the undo adjacent in the source, and assert the state is unchanged after the call returns in tests.

the base case

The base case must describe a complete solution, not merely a state with no remaining options.

In permutation generation completeness is a full-length arrangement; in subset generation every level is complete, which is why subsets are recorded at every node rather than only at leaves.

Subsets record at every node; permutations record only at leaves.

def subsets(a, i, cur, out):
    out.append(cur[:])              # every node is a complete subset
    for j in range(i, len(a)):
        cur.append(a[j]); subsets(a, j + 1, cur, out); cur.pop()

subsets([1, 2], 0, [], out)    # [] [1] [1,2] [2] - four results, not one

Interview trap. Recording only at leaves for a subset problem drops every partial subset, which is most of the answer.

Engineering practice. Decide whether the answer lives at the leaves or at every node, and record accordingly.

pruning is the whole point

Without pruning, backtracking is exhaustive enumeration; pruning is what makes an exponential search tractable on real instances.

A prune rejects a partial candidate that provably cannot extend to a solution, cutting the entire subtree below it.

Check validity at the decision, not at the leaf.

# 8-queens, validate at the leaf: 8^8 = 16,777,216 placements generated.
# Validate on placement: 2,057 nodes explored. Same answer, 8,000x less work.

Interview trap. Testing validity only at the leaves generates the whole tree and discards most of it, which is exponentially more work than pruning early.

Engineering practice. Check validity as soon as each decision is made, and state which constraint the prune enforces.

constraint propagation

A stronger prune deduces further forced values from a decision rather than only rejecting invalid ones.

In a Sudoku solver, placing a digit removes it from the candidate sets of its row, column, and box, which can force other cells immediately.

Record what propagation changed, or the undo is impossible.

trail = []
def assign(cell, digit):
    for peer in peers[cell]:
        if digit in candidates[peer]:
            candidates[peer].discard(digit)
            trail.append((peer, digit))       # so it can be put back
def rollback(mark):
    while len(trail) > mark:
        peer, digit = trail.pop(); candidates[peer].add(digit)

Interview trap. Propagating without recording what was changed makes the undo impossible, so the state is corrupted on backtrack.

Engineering practice. Record every propagated change on a trail, and roll the trail back in the undo step.

ordering the choices

Trying the most constrained variable first, and the least constraining value first, can change the runtime by orders of magnitude.

The most-constrained-variable heuristic reaches contradictions sooner, which prunes larger subtrees earlier in the search.

Most-constrained variable first reaches contradictions sooner.

cell = min(unassigned, key=lambda c: len(candidates[c]))   # fewest options first

On a hard Sudoku this typically cuts explored nodes from hundreds of thousands to a few thousand.

Interview trap. Assuming the ordering only affects constants ignores that it changes the shape of the explored tree, not just the traversal of a fixed one.

Engineering practice. Choose an ordering heuristic deliberately and measure it, since the right one is problem-specific.

generating subsets

The subsets of n elements are generated by a binary decision per element, giving two to the n results.

Each level chooses to include or exclude one element, and the current partial set is a valid subset at every node.

2^n results, so the algorithm cannot beat its own output.

n	subsets	permutations
10	1,024	3,628,800
20	1,048,576	2.4 x 10^18
30	1.07 x 10^9	-

Interview trap. Reporting the algorithm as efficient misses that the output itself is exponential, so no algorithm can do better.

Engineering practice. State that the bound is output-sensitive, and ask whether the caller needs all subsets or only a count or an extremum.

generating permutations

Permutations are generated by choosing an unused element at each level, giving n factorial results.

A used-marker array or an in-place swap both work; the swap version avoids the extra array at the cost of a less obvious undo.

n! is a wall: check it before writing the code.

import math
math.factorial(11)    # 39,916,800 - about a second
math.factorial(13)    # 6,227,020,800 - minutes to hours
math.factorial(20)    # 2.4 x 10^18 - never

Interview trap. Generating permutations for n beyond about eleven exceeds any reasonable time budget, so the approach must be rejected at the design stage rather than optimised.

Engineering practice. Check the factorial growth against the constraint before writing the code, and look for a polynomial formulation when n is large.

duplicates in the input

When the input contains repeated values, distinct results require skipping duplicate choices at the same tree level.

Sorting the input first makes duplicates adjacent, so a level can skip any value equal to the previous one it already tried.

Sort, then skip equal values at the same level.

a.sort()
for j in range(i, len(a)):
    if j > i and a[j] == a[j - 1]: continue     # same level, same value: skip
    ...

# [1, 1, 2] gives [1,1,2], [1,2,1], [2,1,1] - three, not six.

Interview trap. Deduplicating the result set afterwards is correct but does the exponential work first, and it needs a hashable canonical form.

Engineering practice. Sort and skip at the level, and test with an input that is entirely one repeated value.

combinations with a start index

Combinations differ from permutations by fixing an order, which is enforced by passing a start index rather than by filtering results.

Each level may only choose elements at or after the start index, so each combination is generated exactly once in increasing order.

The start index enforces order; it does not filter afterwards.

def combine(n, k, start=1, cur=None):
    if cur is None: cur = []
    if len(cur) == k: out.append(cur[:]); return
    for v in range(start, n + 1):
        cur.append(v); combine(n, k, v + 1, cur); cur.pop()

# C(20, 3) = 1,140 results. Generating 20! permutations and deduplicating is not an option.

Interview trap. Generating permutations and deduplicating by sorting produces the right answer at factorial rather than binomial cost.

Engineering practice. Pass the start index down, and confirm the count matches the expected binomial coefficient in tests.

reuse of elements

Whether an element may be reused is expressed by whether the recursive call advances the index.

Passing the same index allows repetition, and passing the next index forbids it, which is the only difference between the two problem variants.

The index decides repetition; something must still strictly decrease.

combine(candidates, target - v, start=j)      # reuse allowed
combine(candidates, target - v, start=j + 1)  # each element once

# With reuse and a candidate of 0, `target` never decreases: infinite recursion.

Interview trap. Allowing reuse without any decreasing quantity produces infinite recursion when the remaining target does not shrink.

Engineering practice. Ensure some quantity strictly decreases on every recursive call, and state what it is.

the N-queens formulation

N-queens is efficient because the constraints are checked in constant time using sets of occupied columns and diagonals.

The two diagonals are identified by the sum and the difference of the coordinates, so conflict checking needs no scan of the board.

Diagonals are the sum and the difference of the coordinates.

def place(row):
    if row == n: solutions[0] += 1; return
    for col in range(n):
        if col in cols or row + col in diag1 or row - col in diag2: continue
        cols.add(col); diag1.add(row + col); diag2.add(row - col)
        place(row + 1)
        cols.discard(col); diag1.discard(row + col); diag2.discard(row - col)

Constant-time conflict checks; scanning the board would add O(n) per node.

Interview trap. Scanning the board to validate each placement adds a linear factor per node and dominates the search.

Engineering practice. Maintain occupancy sets and update them in the choose and unchoose steps, and place one queen per row by construction.

word search on a grid

Grid path searches mark visited cells during the descent and unmark them on the way out, which is backtracking rather than traversal.

The visited marker is per-path rather than global, because a cell excluded from one path must remain available to another.

Unmark on return - the marker is per path, not global.

grid[r][c] = "#"          # block for this path only
found = any(dfs(nr, nc, i + 1) for nr, nc in neighbours(r, c))
grid[r][c] = original     # restore, so another path may use this cell

Interview trap. Using a global visited set, as in a connectivity traversal, wrongly blocks cells that a different path could legitimately use.

Engineering practice. Unmark on return, and be able to explain why this differs from the global marking used in connected-component searches.

memoisation versus backtracking

Backtracking with overlapping subproblems becomes dynamic programming once the state is memoised.

The conversion requires the answer to depend only on a compact state, which is what makes a cache key possible.

Memoise only when the state is compact and repeats.

from functools import cache

@cache
def ways(i, remaining):       # small state: two integers - repeats constantly
    ...

# @cache on (i, tuple(path)) would never hit: no two states are equal.

Interview trap. Memoising a search whose state includes the whole path gains nothing, since no two states repeat.

Engineering practice. Identify the minimal state the answer depends on; if it is small, memoise, and if it is the path itself, prune instead.

counting versus enumerating

Counting solutions is often polynomial when enumerating them is exponential, and the two must not be conflated.

Counting can aggregate over states with dynamic programming, while enumeration must produce every result and is bounded below by the output size.

Counting can be polynomial where enumeration is exponential.

# Number of paths in an m x n grid, moving right and down:
math.comb(m + n - 2, m - 1)      # closed form, instant
# Enumerating them at m = n = 20 means 35,345,263,800 paths.

Interview trap. Enumerating in order to count discards the polynomial algorithm and fails on inputs the counting version handles easily.

Engineering practice. Read the question carefully: if only a count or an optimum is needed, look for the aggregating formulation.

the cost of copying state

Copying the partial solution at every node adds a factor proportional to its length, which can dominate the search.

Mutating one shared structure with an explicit undo avoids the copy, at the cost of copying only when a complete solution is recorded.

Copy once, when recording; appending the live list stores aliases.

out.append(cur)        # wrong: every entry aliases the same list, ending up []
out.append(cur[:])     # right: one copy per recorded solution

Interview trap. Appending the shared mutable structure to the results without copying stores references that later mutations overwrite, leaving a result list of identical entries.

Engineering practice. Mutate during the search and copy exactly once when recording a solution.

recursion depth

Backtracking depth equals the number of decisions, which is usually the input size rather than its logarithm.

A search over a thousand-element input recurses a thousand levels deep, which exceeds default recursion limits in several languages.

Depth equals the number of decisions, usually n.

# A subset search over 5,000 items recurses 5,000 deep: RecursionError at ~1,000.
stack = [(0, [])]
while stack: ...        # explicit stack instead

Interview trap. Raising the recursion limit converts a clean exception into a native stack overflow that terminates the process.

Engineering practice. Convert to an explicit stack when the depth is bounded only by input size, and test at the documented maximum.

iterative deepening

Iterative deepening gets breadth-first optimality with depth-first memory, by repeating a bounded depth-first search with increasing limits.

The repeated work is dominated by the last level in a tree with branching factor above one, so the overhead is a constant factor rather than an order.

Repeated work is a constant factor when the branching factor exceeds one.

# Branching factor 10, depth 5: levels cost 10 + 100 + 1,000 + 10,000 + 100,000.
# The last level is 90% of the total, so re-expanding the earlier ones costs ~11%.

Interview trap. Dismissing it because it repeats work ignores that the repetition is bounded by the branching factor, which is usually a small multiplier.

Engineering practice. Use it when the frontier of a breadth-first search would not fit in memory but the depth bound is known to be modest.

branch and bound

For optimisation rather than enumeration, a bound on the best achievable result from a partial candidate prunes subtrees that cannot beat the incumbent.

The bound must be optimistic — never worse than the true best in that subtree — or a correct solution can be pruned away.

The bound must be optimistic, or a correct solution is pruned away.

if best_possible_from(state) <= incumbent: return    # safe only if the estimate
                                                     # never understates the true best

A bound that is occasionally pessimistic makes the search faster and the answer silently wrong.

Interview trap. A bound that is occasionally pessimistic makes the search faster and the answer wrong, and the error is silent.

Engineering practice. Prove the bound's optimism, and validate against exhaustive search on small instances.

symmetry breaking

Many search spaces contain symmetric solutions, and eliminating the symmetry cuts the search by the size of the symmetry group.

Fixing the first queen to the left half of the board, or requiring a canonical ordering within a group, removes equivalent branches without losing solutions.

Halve the search, then verify the solution count against the unbroken search.

# N-queens: the first queen may be restricted to the left half of the first row,
# then the count doubled (with care for the odd middle column).
# Verify against the full search for n = 6..9 before trusting it.

Interview trap. An unsound symmetry rule removes genuine solutions, and validating against a full search on small instances is the only reliable check.

Engineering practice. State the symmetry precisely, apply the canonical-form rule, and verify the solution count against the unbroken search for small n.

worst case versus practical performance

Backtracking's worst case is exponential regardless of pruning, and good pruning changes typical performance rather than the bound.

Real instances often have structure that pruning exploits, which is why constraint solvers handle problems whose worst case is intractable.

Pruning changes typical time, not the bound.

# SAT solvers routinely decide instances with 10^6 variables.
# SAT is still NP-complete. Both statements are true, and the second is the bound.

Interview trap. Presenting a heavily pruned search as polynomial confuses observed performance with a proven bound.

Engineering practice. Quote the exponential worst case, then describe the pruning and the instance sizes it handles in practice.

bounding the work

A backtracking search over untrusted input needs an explicit node or time budget, because the input controls the search size.

Without a budget, a crafted input turns a request into an unbounded computation, which is a denial-of-service vector.

Count nodes against a budget; a request timeout is not a bound.

NODE_BUDGET = 2_000_000
nodes = 0
def search(...):
    global nodes
    nodes += 1
    if nodes > NODE_BUDGET: raise SearchExhausted

Interview trap. Relying on a transport timeout can leave the worker running after the client has gone away, consuming the resource the timeout was meant to protect.

Engineering practice. Count expanded nodes against a limit and return a partial or refused result when it is exceeded.

testing a backtracking solution

The defects concentrate in the undo step and in the duplicate-skipping rule, both of which show up as wrong result sets rather than crashes.

Comparing the result set against a brute-force generator on small inputs catches both, as does asserting the expected result count.

Assert completeness, not just validity.

for n in range(1, 8):
    a = [random.randint(0, 2) for _ in range(n)]
    assert sorted(map(sorted, my_subsets(a))) == sorted(map(sorted, brute_force(a)))

Checking only that each returned result is valid misses the results that are missing.

Interview trap. Checking only that every returned result is valid misses missing results entirely, which is the more common defect.

Engineering practice. Assert both validity and completeness, and include an all-duplicates input in the suite.

library generators

Standard libraries provide permutation, combination, and product generators that are lazy and correct.

They stream results rather than materialising them, which keeps memory bounded even when the output is exponential.

Lazy, correct, and C-speed; consume them without materialising.

from itertools import permutations, combinations, product
next(p for p in permutations(a) if valid(p))     # stops at the first hit
list(permutations(range(12)))                    # 479,001,600 tuples: do not

Interview trap. Materialising a library generator into a list reintroduces the memory problem the generator avoided.

Engineering practice. Consume generators lazily with an early exit, and hand-write the search only when it needs problem-specific pruning.

recognising a backtracking problem

Backtracking fits when the answer is a sequence of decisions, the constraints can reject partial candidates, and no polynomial formulation exists.

If the state is compact and subproblems repeat, dynamic programming is better; if a local rule is provably optimal, greedy is better.

Sequence of decisions, prunable partials, no polynomial formulation.

Signal	Technique
Compact state, subproblems repeat	dynamic programming
A local rule is provably optimal	greedy
Enumerate all valid configurations	backtracking
Count configurations only	often a closed form or DP

Interview trap. Reaching for backtracking on a problem with an aggregating recurrence produces an exponential solution to a polynomial problem.

Engineering practice. Check for overlapping subproblems and for a provable greedy choice first, and use backtracking when neither exists.