The template
Nearly every backtracking problem fits this shape:
solve(state):
if state is complete: record it, return
for each candidate c:
if c is not valid here: continue ← pruning
apply c to state
solve(state)
undo c from state ← the backtrack
The validity check is the entire performance story. Without it you are enumerating every possibility; with it you discard whole subtrees before exploring them.
How much pruning buys you
The eight queens problem asks for eight queens on a chessboard with none attacking another. Placing eight pieces on 64 squares gives about 4.4 billion arrangements. Restricting to one queen per column cuts it to 88 = 16.7 million. Checking rows and diagonals as you place each queen — abandoning a branch the moment two queens conflict — brings the actual number of positions examined down to roughly 15,000.
Same search space, same guarantee of finding every solution, five orders of magnitude less work. The algorithm did not get cleverer about queens; it just stopped exploring branches that were already known to fail.
Try, recurse, undo
Backtracking explores a space of partial solutions. At each step it makes a choice, recurses, and then undoes the choice before trying the next one.
That undo step is what distinguishes it from plain recursion, and it is what makes exhaustive search possible with a single shared state rather than a copy per branch.
def permutations(items):
result, current, used = [], [], [False] * len(items)
def backtrack():
if len(current) == len(items):
result.append(current[:]) # copy - current keeps changing
return
for i, item in enumerate(items):
if used[i]:
continue
current.append(item); used[i] = True # choose
backtrack() # explore
current.pop(); used[i] = False # UNDO
return
backtrack()
return result
Three lines carry the whole pattern: choose, explore, undo. Every backtracking solution has that shape, and the current[:] copy on line 6 is the detail people miss — appending current itself stores a reference to a list that will keep changing.
Pruning is what makes it feasible
Without pruning, backtracking is brute force with a stack. With pruning, it is often practical on spaces that are astronomically large.
The n-queens problem places n queens on an n×n board with none attacking another. There are 64 choose 8 = 4.4 billion arrangements for n = 8. Backtracking with pruning examines about 15,000 positions.
The saving comes from abandoning a branch the moment it cannot succeed:
def solve_queens(n):
cols, diag1, diag2 = set(), set(), set()
board, out = [], []
def place(row):
if row == n:
out.append(board[:])
return
for col in range(n):
if col in cols or (row-col) in diag1 or (row+col) in diag2:
continue # PRUNE - cannot possibly work
cols.add(col); diag1.add(row-col); diag2.add(row+col)
board.append(col)
place(row + 1)
board.pop()
cols.discard(col); diag1.discard(row-col); diag2.discard(row+col)
place(0)
return out
The three sets are the pruning mechanism, and the diagonal encoding is the neat part: all squares on a descending diagonal share row - col, and all on an ascending diagonal share row + col. That turns an O(n) attack check into O(1).
Better pruning beats a faster machine. That is the practical lesson of this whole topic.
Recognising a backtracking problem
The signals:
- The answer is a sequence of choices — a permutation, a subset, an assignment, a path.
- Choices constrain later choices.
- You need all solutions, or one satisfying constraints, rather than an optimum computed from subproblems.
- The state can be undone cheaply.
| Problem | Choice at each step |
|---|
| Permutations | Which unused item comes next |
| Subsets | Include this item or not |
| N-queens | Which column in this row |
| Sudoku | Which digit in this cell |
| Word search | Which adjacent cell to move to |
| Graph colouring | Which colour for this vertex |
| Combination sum | Which candidate to add next |
If the problem instead asks for a maximum or a count computable from overlapping subproblems, dynamic programming is usually the better tool — it reuses work where backtracking re-derives it.
What pruning is worth, counted
Backtracking is brute force that gives up early, and "gives up early" is doing all the work. N-Queens is the standard example because the saving is enormous and easy to count: the same search, with and without the check that rejects a partial placement.
Things to try
- Watch a path get committed. Press Step repeatedly. The search extends along a single route, taking the first available direction each time — the same depth-first commitment as DFS.
- Catch the undo. Keep stepping until the path hits a dead end. Watch cells get unmarked as the search retreats. That erasure is the backtrack, and it is what frees those cells for a different attempt.
- Watch it re-use a corridor. After a retreat, notice the search often re-enters territory it just abandoned, this time turning a different way. The state was properly restored, which is exactly why that is possible.
- Compare mazes. Press New Maze a few times and Run each. Open mazes with many branches cause far more backtracking than corridor-like mazes, where there is rarely a choice to get wrong.
Where it is used
- Constraint solvers — SAT solvers, scheduling, timetabling. Backtracking with sophisticated pruning is the core of DPLL, which underlies modern SAT solving.
- Puzzles — sudoku, crosswords, n-queens, knight's tour.
- Regular expression matching — backtracking regex engines try alternatives and undo, which is also why pathological patterns can take exponential time.
- Parsing — recursive descent with backtracking for ambiguous grammars.
- Compiler register allocation as graph colouring.
- Test generation and combinatorial coverage.
The regex point is worth noting because it has real security implications: catastrophic backtracking on adversarial input is a denial-of-service vector, which is why some engines use non-backtracking automata instead.
What trips people up
- Not undoing the state. The single most common bug. If you mark a cell, recurse, and forget to unmark it on failure, later branches see phantom occupied cells and valid solutions get missed.
- Pruning too late. Checking validity only when the solution is complete turns backtracking back into brute force. Check at every step, as early as the constraint allows.
- Passing mutable state by reference and recording it directly. When a solution is found, store a copy. Storing the live object means the backtracking that follows mutates your recorded answer.
- Expecting it to be fast in the worst case. Pruning improves the typical case, not the bound — worst-case complexity is still exponential. If pruning is weak, so is the algorithm.
In one line
Backtracking explores the space of partial solutions depth-first, abandoning a branch as soon as it violates a constraint and undoing its state on the way back out. The undo is what makes it correct and the early constraint check is what makes it fast — without pruning it is exhaustive search, and with it, problems with billions of arrangements resolve in thousands of steps. The complexity remains exponential in the worst case; the art is in pruning hard enough that the worst case rarely arrives.
Avoiding duplicate results
A recurring difficulty: when the input contains duplicates, naive backtracking produces the same solution several times.
The standard fix is to sort the input and skip a candidate that equals its predecessor at the same recursion depth:
def subsets_with_dup(nums):
nums.sort()
out, cur = [], []
def go(start):
out.append(cur[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue # skip duplicates at this level
cur.append(nums[i])
go(i + 1)
cur.pop()
go(0)
return out
The condition i > start is precise and easy to get wrong: it skips a repeated value only when it is a sibling choice at the same level, not when it is used deeper in the same branch. Writing i > 0 instead would incorrectly exclude legitimate solutions containing the value twice.
Complexity, and what to expect
Backtracking is exponential in general, and the exponent depends on the problem's shape.
| Problem | Complexity |
|---|
| Permutations of n | O(n! × n) |
| Subsets of n | O(2ⁿ × n) |
| N-queens | O(n!) worst case, far less with pruning |
| Sudoku | Exponential; instant in practice with good pruning |
| Combination sum | Depends on the target and candidates |
The gap between worst case and practice is the whole point. Sudoku's search space is enormous and a constraint-propagating solver finishes a newspaper puzzle in milliseconds, because most branches die immediately.
Two techniques beyond basic pruning:
Constraint propagation. After each choice, deduce forced consequences — a Sudoku cell with only one possible digit must take it. This can solve many puzzles with almost no search.
Ordering heuristics. Choose the most constrained variable next (the cell with fewest candidates), so failures are discovered early rather than deep in the tree.
Questions people ask
What is the difference from brute force? Backtracking prunes branches that cannot lead to a solution. Brute force enumerates everything.
How is it different from DFS? It is DFS over a state space, with explicit undo and pruning.
When should I use DP instead? When subproblems overlap and you want an optimum or a count. Backtracking enumerates; DP reuses.
Why do I need to copy the current state? Because it is mutated in place. Storing a reference gives you a list that changes underneath you.
How do I stop after the first solution? Return a boolean up the recursion and stop exploring once it is true.
Why is my solution too slow? Almost always insufficient pruning. Add constraints that fail earlier, and order choices so failures are found sooner.
Recap in one screen
- Choose, explore, undo — the undo is what distinguishes backtracking from ordinary recursion.
- Pruning is what makes it practical: n-queens goes from billions of arrangements to thousands of positions.
- Copy the state when recording a solution, or you store a reference to something still changing.
- Sort and skip equal siblings to avoid duplicate results on duplicate input.
- Constraint propagation and choosing the most constrained variable next are the two upgrades that matter.