Backtracking: Search by Trying and Undoing
How backtracking builds answers one choice at a time and drops dead ends early. For 8-queens it visited 2,057 states, not 16,777,216 raw placements, and found all 92 solutions.
Backtracking is depth-first search over choices: build a solution step by step and undo the last choice as soon as the partial answer cannot lead to a valid result. The detail interviewers expect is pruning. For 8-queens, checking each row cut the search to 2,057 visited states, against 19,173,961 with no checks, and still found all 92 solutions.
Backtracking builds a solution step by step and undoes the last choice when it hits a dead end. Pruning bad branches early is what makes it practical. For 8-queens it visited 2,057 states and found all 92 solutions, where blind placement has 16,777,216 possibilities. It fits puzzles, subsets and permutations.
- Backtracking follows one template: choose an option, recurse to the next decision, then undo the choice and try the next option when the path fails.
- For 8-queens, backtracking with sets for columns and diagonals visited 2,057 states and found all 92 solutions, against 19,173,961 states when nothing is checked until the board is full.
- In subset sum with positive numbers, the check total > target prunes a whole branch, and [2, 3, 5, 7] with target 10 returns [[2, 3, 5], [3, 7]].
- Duplicate results from repeated input values are avoided by sorting and skipping an equal value at the same recursion level; subsets of [1, 2, 2] drop from 8 to 6.
- Backtracking has no polynomial guarantee: subset sum on n numbers explores up to 2^n branches, and generating all permutations is n!.
- Dynamic programming suits overlapping subproblems that need one best value or a count, while backtracking suits problems where the actual solutions must be listed.
01The idea
Backtracking explores a decision tree depth first. At each step you pick one option, continue to the next decision, and if that path fails, undo the option and try the next one. Think of walking a maze and returning to the last junction when you hit a wall. If you know depth-first search on graphs, this is the same walk, except the tree is never stored. It exists only as the call stack.
Every backtracking solution is three moves wrapped in a loop: choose, explore, un-choose.
def backtrack(state):
if is_complete(state):
record(copy_of(state))
return
for option in options(state):
if not is_valid(state, option):
continue # prune before recursing
apply(state, option) # choose
backtrack(state) # explore
remove(state, option) # un-chooseThe un-choose line gives the technique its name. One mutable state is shared by the whole search, so after the recursive call returns it must look exactly as it did before apply, leaving the next option a clean slate. The is_valid check is where the speed comes from: an option rejected here never gets a recursive call, so nothing below it is ever built.
02Tracing 4-queens by hand
Walk n=4 by hand first. Queens go one per row, so the only decision is the column. Number the rows and columns 0 to 3.
Row 0 takes column 0. In row 1, columns 0 and 1 are attacked (same column, then diagonal), so column 2 is the first safe choice. Now row 2 is stuck. Column 0 shares a column with the first queen, column 2 shares a column with the second, and columns 1 and 3 sit on the second queen's diagonals. No option survives, so the call returns, and row 1 un-chooses column 2 and moves to column 3.
That gets one level further. Row 2 can take column 1, but then every square in row 3 is attacked. Back up again: row 2 tries columns 2 and 3, both attacked. Row 1 has no columns left. So row 0 un-chooses column 0 and tries column 1.
This time the search runs straight through: row 1 at column 3, row 2 at column 0, row 3 at column 2. The first solution, written as the column for each row, is (1, 3, 0, 2). It took 9 visited states to reach it, out of 17 for the complete n=4 search that also finds the mirror solution (2, 0, 3, 1). Each dead end cost only the work below one node. The search built two complete boards, where blind placement would enumerate all 256.
03Example: subset sum
def subsets_with_sum(nums, target):
result = []
def go(i, chosen, total):
if total == target:
result.append(chosen[:]) # copy, chosen keeps changing
return
if i == len(nums) or total > target:
return # dead end: stop early
chosen.append(nums[i]) # choose
go(i + 1, chosen, total + nums[i])
chosen.pop() # undo
go(i + 1, chosen, total) # skip this number
go(0, [], 0)
return resultFor [2, 3, 5, 7] and target 10 it returns [[2, 3, 5], [3, 7]]. The check total > target is pruning: once the running total is too large, no extension can fix it, so the whole branch is dropped (this works because the numbers are positive). Two details trip people up: you must copy chosen when saving it, and you must pop after the recursive call.
04Example: N-Queens
def n_queens(n):
cols, d1, d2 = set(), set(), set()
count = states = 0
def place(row):
nonlocal count, states
states += 1
if row == n:
count += 1
return
for c in range(n):
if c in cols or (row - c) in d1 or (row + c) in d2:
continue # attacked: prune
cols.add(c); d1.add(row - c); d2.add(row + c)
place(row + 1)
cols.remove(c); d1.remove(row - c); d2.remove(row + c)
place(0)
return count, statesOne queen per row is built in, so the loop only chooses the column. Three sets record which columns and diagonals are taken, which makes the attack check constant time. The removal line mirrors the add line. Drop one removal and later rows see phantom attacks, so the search quietly misses solutions instead of crashing.
05How much does pruning save?
Here is what the code returned: solutions found and states visited, compared with n to the power n for placing a queen in any column of every row with no checks.
n=4: 2 solutions, 17 states, against 256
n=5: 10 solutions, 54 states, against 3,125
n=6: 4 solutions, 153 states, against 46,656
n=7: 40 solutions, 552 states, against 823,543
n=8: 92 solutions, 2,057 states, against 16,777,216
The solution counts match the known values for N-Queens (2, 10, 4, 40, 92). The saving grows fast because killing a branch near the top removes everything beneath it.
Counting n^n leaves understates what blind search really costs, because a search tree also has inner nodes. To measure it, I ran three versions of 8-queens in Python 3.13 and counted every call:
no checks until the board is full 19,173,961 states 9.72 s
columns kept distinct, diagonals at end 109,601 states 0.077 s
columns and diagonals checked per row 2,057 states 0.0023 sAll three found the same 92 solutions. The timings come from one run on a small 2-core sandbox and will differ on your machine; the state counts will not. Forcing distinct columns alone turns the problem into permutations (8! = 40,320 full boards), and that already removes over 99 percent of the blind tree. Checking the diagonals as each queen lands cuts the remaining work by another factor of about 53. Test each constraint at the earliest step where it can fail.
06Problem families and common bugs
Most interview backtracking problems take one of four shapes, and the shape tells you the loop and the base case.
Subsets. Each element is a yes-or-no decision, so the tree is binary with depth n and 2^n leaves. For [1, 2, 3] the include-first order gives [1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], [].
Permutations. Each level picks any unused element, tracked with a boolean array. Three elements give 6 orderings, and the leaf count is n!.
Combination sum. Pick numbers, reuse allowed, to hit a target. Passing the current index down (not index + 1) allows reuse while keeping each combination in sorted order, so [2, 3] and [3, 2] are not both produced. With sorted candidates, break out of the loop once a candidate exceeds what is left. For candidates [5, 2, 3] and target 8 the result is [2, 2, 2, 2], [2, 3, 3], [3, 5].
Grid puzzles. Sudoku fills one empty cell at a time with a digit not already in its row, column or 3x3 box. Word search marks each visited cell and unmarks it on the way back.
Three bugs cause most wrong answers, and I reproduced each one on the subsets code:
- Forgetting to undo. Remove the
pop()and the list keeps growing across branches. For [1, 2, 3] the output contained [1, 2, 3, 3, 2, 3, 3], a "subset" with seven elements. - Saving a reference instead of a copy. Append
curinstead ofcur[:]and all 8 saved results point to the same list, which is empty by the time the search ends: eight copies of []. - Duplicate input values. Subsets of [1, 2, 2] came out as 8 lists with [1, 2] and [2] each appearing twice. The fix: sort, then skip a value equal to the one just tried at the same level (
if j > start and nums[j] == nums[j - 1]: continue). That produced the 6 distinct subsets.
07Complexity and designing your own
Pruning helps, but backtracking has no polynomial guarantee. Subset sum on n numbers explores up to 2^n branches, and generating all permutations is n!. It works well when constraints cut the search quickly, and badly when they do not.
State cost in an interview as nodes visited times work per node. Subsets have 2^n leaves, each copied in O(n), so O(n x 2^n); permutations are O(n x n!). Extra memory, output aside, is O(n) for the recursion and partial answer. When every answer must be listed, the output size is a floor no algorithm can beat.
If the problem has overlapping subproblems, such as subset sum with small target values, dynamic programming is often far faster. Use backtracking when you need all solutions, or the constraints are too tangled for a table.
To design one from scratch, ask four questions. What is one decision? (a column, include or skip, next letter). What makes a choice invalid? (that is your pruning test). When is the answer complete? (the base case). How do I undo a choice? (the cleanup line after the recursive call).
Then order choices so failures show up early, and keep per-step checks cheap with sets or counters instead of rescanning.
08Common interview questions
Q: What is backtracking?
A: Depth-first search over choices that abandons a path as soon as it cannot lead to a valid answer.
Q: How is it different from brute force?
A: Brute force generates every full candidate and checks it. Backtracking checks while building and prunes early. For 8-queens, checking only at the end visited 19,173,961 states; checking each row as it was filled visited 2,057, with the same 92 solutions.
Q: Why copy the list when saving a result?
A: The same list is modified as the search continues, so you would store a reference that later changes. In the subsets test every saved result ended up as the same empty list.
Q: How do you avoid duplicate results when the input has repeated values?
A: Sort the input, then at each recursion level skip a value equal to the previous one tried at that level. Subsets of [1, 2, 2] drop from 8 lists to the 6 distinct ones.
Q: What is the time complexity of generating all permutations?
A: There are n! leaves and copying each answer costs O(n), so O(n x n!) time and O(n) extra space for the recursion and the current permutation.
Q: Backtracking or dynamic programming?
A: DP when subproblems overlap and you need one best value or a count. Backtracking when you need to list actual solutions.