The textbook line on backtracking is "try everything and undo what doesn't work." Accurate, and useless. It tells you nothing about how to write a solution to a problem you've never seen. Backtracking isn't trial and error. It's a depth first walk over a state space tree with a rule for quitting a branch the moment it can't lead anywhere valid.
Once you see it that way, the trick stops being clever and starts being mechanical. Every backtracking problem you'll meet runs the same loop. The only thing that changes is what you're choosing and what counts as a dead branch.
TL;DR: Backtracking builds a solution one decision at a time and walks a state space tree with DFS. When a partial solution breaks a constraint, you abandon that branch and try the next option. The whole algorithm is choose, check, undo. The variation between problems is what you choose and what the constraints are.
What backtracking actually is
Picture a tree where the root is the empty solution. Each edge is a decision: place a queen in a column, add a character to a string, include an element in a subset. Each node is the partial solution you have so far. Leaves are either complete valid answers or dead ends where a constraint already broke.
Exhaustive search builds every leaf and checks each one after the fact. Backtracking checks on the way down and stops descending the instant a partial answer is doomed. On a board with n queens, exhaustive search inspects all n^n configurations. Backtracking inspects a sliver of that, because it never places a queen in a row where a conflict already exists.
For tiny inputs the difference is academic. Generate every subset of a 10 element array and pruning saves you nothing, there's nothing to prune. The advantage shows up when constraints are tight and the search space is large, which is exactly the shape of the problems interviewers like.
The choose, check, undo skeleton
Strip away the problem specifics and every backtracking routine does three things in a loop:
- Choose: extend the current partial solution with one option.
- Check: test whether that extension violates a constraint. If it does, don't recurse into it.
- Undo: after the recursive call returns, reverse the choice so the next option starts from a clean state.
That last step is the one people forget, and it's the one that quietly produces wrong answers instead of crashes. If you append to a path or flip a visited flag and never reverse it, later branches inherit corrupted state from earlier ones.
Walking N-Queens by hand
N-Queens is the cleanest place to watch this run. Place n queens on an n x n board so none attack each other, no shared row, column, or diagonal. The tree has n levels, one per row, and at each level you pick a column. The branching factor starts at n and shrinks as conflicts knock out columns.
Here's a partial trace for n=4, watching where pruning kicks in:
Row 0: try column 0
Row 1: column 0 -> PRUNE (same column)
Row 1: column 1 -> PRUNE (diagonal with row 0)
Row 1: column 2 -> ok, partial [0, 2]
Row 2: every column conflicts -> BACKTRACK
Row 1: column 3 -> ok, partial [0, 3]
Row 2: column 1 -> ok, partial [0, 3, 1]
Row 3: every column conflicts -> BACKTRACK
...all of row 1's options exhausted -> BACKTRACK
Row 0: try column 1
Row 1: column 3 -> [1, 3]
Row 2: column 0 -> [1, 3, 0]
Row 3: column 2 -> [1, 3, 0, 2] -> SOLUTION
Without pruning you'd evaluate all 4^4 = 256 placements. With it, the algorithm touches roughly 20 nodes before the first solution. Early constraint checks did the heavy lifting. The code is just the skeleton with the constraint filled in:
def solve_n_queens(n):
solutions = []
board = []
def is_valid(row, col):
for prev_row, prev_col in enumerate(board):
if prev_col == col:
return False
if abs(prev_row - row) == abs(prev_col - col):
return False
return True
def backtrack(row):
if row == n:
solutions.append(board[:])
return
for col in range(n):
if is_valid(row, col):
board.append(col) # choose
backtrack(row + 1) # explore
board.pop() # undo
backtrack(0)
return solutions
board.append(col) is the choose. is_valid(row, col) is the check that prunes. board.pop() is the undo. The domain looks completely different on Sudoku or word search, but the three pieces are always sitting right there.
The three shapes backtracking takes
Backtracking problems aren't all the same. They sort into three shapes by how much you can prune:
- Unconditional enumeration. Produce every arrangement with no extra rule: all subsets, all letter combinations of a phone number. The tree branches at every position and every leaf is valid output. Nothing to prune, you walk the whole tree.
- Conditional enumeration. Same branching shape, but a constraint kills branches mid construction: valid parentheses, combinations that sum to a target, permutations of distinct elements. Some branches die before the leaf because the partial answer already broke the rule.
- Backtracking search. Find one or more configurations that satisfy a global constraint: N-Queens, Sudoku, maze pathfinding. Pruning is heaviest here because each placement constrains every later one.
The reason this taxonomy is worth memorising: it tells you how aggressive your pruning should be before you write a line. Search problems want constraint checks at every level. Unconditional enumeration wants none, and adding them just slows you down.
To see the same skeleton with no pruning at all, here's generating every subset of an array. Every node is already a valid answer, so there's nothing to check:
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:]) # every node is a subset
for i in range(start, len(nums)):
path.append(nums[i]) # choose
backtrack(i + 1, path) # explore
path.pop() # undo
backtrack(0, [])
return result
Same three pieces. The is_valid check from N-Queens is simply absent, because in unconditional enumeration there's no constraint to prune on. Drop the path.pop() line, though, and you reproduce the most common backtracking bug: every subset after the first comes back polluted with elements left over from an earlier branch. The undo is what keeps one mutable list honest across the whole tree.
One more thing the shapes tell you is the cost. The worst case for backtracking is exponential, because the tree can have exponentially many nodes. Pruning doesn't change that worst case, it changes how much of it you actually visit. On loose constraints you walk most of the tree anyway. On tight ones like N-Queens you skip the overwhelming majority, which is why the same algorithm feels fast on one problem and hopeless on another.
When backtracking is the wrong call
Reaching for backtracking on the wrong problem is a common interview misstep. Three signals tell you it fits:
- The problem wants all valid configurations, or one valid configuration. "Generate all", "find every", "place the" are tells. If it only wants a count, DP is usually faster.
- Each decision constrains future decisions. Placing an element at A removes options at B. That's a constrained search tree.
- There's no greedy shortcut and no overlapping subproblem to cache. If locally optimal choices give the global optimum, that's greedy. If the same subproblem repeats, that's DP.
When the input is large and you can't prune hard, even correct backtracking times out. That's the boundary where the interviewer is usually steering you toward dynamic programming.
A quick gut check before you commit: estimate the branching factor and the depth. If the tree is roughly b choices deep d levels and your constraints don't kill many branches, you're looking at something near b^d work. When that number is astronomical and the problem only wants a count or a single optimal value, that's the cue to stop and ask whether the states overlap.
Where backtracking turns into DP
The two are closer than they look. When a backtracking solution explores the same partial state through different decision paths, you're recomputing work. Cache those states and top down DP falls out of the same recursion you already wrote.
That progression, from raw search to memoised recursion to a table, is one of the most reusable moves in interview prep. It also explains why solid recursion has to come first. Backtracking is recursion with a choose, check, undo wrapper, so if the recursive call still feels shaky, the wrapper won't save you. If you want to drill the pattern shapes directly, the backtracking pattern lessons work through each of the three with their own trigger checklist.
The gap that trips most people up isn't writing the recursion. It's trusting the moment a branch should be abandoned, and that's the part I keep coming back to in my own work.
I wrote a longer version on my blog that walks through the other two shapes with full code, plus the common bugs that make backtracking silently return wrong answers.
Which backtracking problem finally made the choose, check, undo loop click for you?
Top comments (0)