Backtracking
Explore choices one at a time, undo them when they fail, and prune whole branches early. Subsets, permutations, and N-Queens.
intermediate45 min#backtracking#recursion#search#pruning
Prerequisites: Recursion
Why it matters
Some problems ask you to build something out of many choices: every arrangement, every valid combination, every way to fill a grid. There is no formula; you have to search. Backtracking is the disciplined way to search. It powers puzzle solvers (Sudoku, N-Queens), combinatorial generators, parsing with alternatives, and constraint solvers. It is also a staple interview topic because it tests whether you can manage state cleanly through recursion.
Intuition
Imagine walking a maze with a ball of string. At each fork you pick a corridor and keep walking. If you hit a dead end, you rewind the string to the last fork and try the next corridor. You never forget what you tried, and you never walk the same path twice.
Backtracking is a depth-first walk over a decision tree. Each level is one decision; each branch is one option. A full path from root to leaf is one complete candidate. The art is cutting off branches that cannot possibly lead to a valid answer, as early as you can.
How it works
Almost every backtracking solution has the same skeleton:
- State: a partial solution (
path) plus anything needed to check validity. - Base case: if the partial solution is complete, record a copy of it.
- Choices: loop over the options available at this step.
- Choose, explore, unchoose: apply the option, recurse, then undo it so the next option starts from a clean state.
- Prune: skip an option as soon as it violates a constraint.
subsets of [1, 2] (take or skip each item)
start
/ \
skip 1 take 1
/ \ / \
skip 2 take 2 skip 2 take 2
[] [2] [1] [1,2]
Here is that depth-first walk over the subsets of [1, 2, 3]. Each node is the current path.
Green is the current path, amber is already explored. Each backtrack is the undo step (pop) returning to a parent. All 8 subsets are visited exactly once.
The undo step is what makes it backtracking. Because path is shared and mutated, you must append a copy when you record an answer, or every stored result will end up pointing at the same list.
Pruning is where the savings are. Plain enumeration of N-Queens places one queen per row in any of n columns: n^n boards. Rejecting a square the moment it shares a column or diagonal with an earlier queen cuts the tree enormously. The worst case is still exponential, but the practical work is a tiny fraction.
To see pruning, look for combinations of the distinct numbers 2, 3, 4 (each used at most once, in increasing order) that sum to 6. Each node shows its path and running sum.
For N-Queens, two squares share a diagonal when row - col is equal (one direction) or row + col is equal (the other). Keeping three sets (columns, both diagonals) makes each check O(1).
A 4 by 4 board shows the same rhythm of place, fail, and undo. Queens are green; amber squares were rejected in that row.
One queen per row, left to right. When a row has no safe square the search steps back and moves an earlier queen. Pruning stops each doomed branch immediately.
| Operation | Time | Notes |
|---|---|---|
| All subsets | O(2^n * n) | 2^n leaves, copying a path costs up to n |
| All permutations | O(n! * n) | n! leaves |
| N-Queens (with pruning) | Exponential | Far below n^n in practice |
| Recursion depth / space | O(n) | One frame per decision, excluding output |
Code: subsets, permutations, N-Queens
def subsets(nums):
out, path = [], []
def go(i):
if i == len(nums):
out.append(path[:]) # copy, path keeps mutating
return
go(i + 1) # choice 1: skip nums[i]
path.append(nums[i]) # choice 2: take it
go(i + 1)
path.pop() # undo
go(0)
return out
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
def count_queens(n):
cols, diag1, diag2 = set(), set(), set()
def place(row):
if row == n:
return 1
total = 0
for c in range(n):
if c in cols or row - c in diag1 or row + c in diag2:
continue # prune: square is attacked
cols.add(c); diag1.add(row - c); diag2.add(row + c)
total += place(row + 1)
cols.remove(c); diag1.remove(row - c); diag2.remove(row + c)
return total
return place(0)
print(len(subsets([1, 2, 3])), " ".join(map(str, subsets([1, 2, 3])[-1])))
print(" ".join("".join(map(str, p)) for p in permutations([1, 2, 3])))
print(count_queens(4), count_queens(6), count_queens(8))function subsets(nums) {
const out = [], path = [];
function go(i) {
if (i === nums.length) {
out.push([...path]); // copy, path keeps mutating
return;
}
go(i + 1); // choice 1: skip nums[i]
path.push(nums[i]); // choice 2: take it
go(i + 1);
path.pop(); // undo
}
go(0);
return out;
}
function permutations(nums) {
const out = [], path = [], used = new Array(nums.length).fill(false);
function go() {
if (path.length === nums.length) {
out.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]);
go();
path.pop();
used[i] = false;
}
}
go();
return out;
}
function countQueens(n) {
const cols = new Set(), diag1 = new Set(), diag2 = new Set();
function place(row) {
if (row === n) return 1;
let total = 0;
for (let c = 0; c < n; c++) {
if (cols.has(c) || diag1.has(row - c) || diag2.has(row + c)) continue; // prune
cols.add(c); diag1.add(row - c); diag2.add(row + c);
total += place(row + 1);
cols.delete(c); diag1.delete(row - c); diag2.delete(row + c);
}
return total;
}
return place(0);
}
const s = subsets([1, 2, 3]);
console.log(s.length, s[s.length - 1].join(" "));
console.log(permutations([1, 2, 3]).map((p) => p.join("")).join(" "));
console.log(countQueens(4), countQueens(6), countQueens(8));Both versions print three lines: 8 1 2 3 (eight subsets, the last of which is 1 2 3), then 123 132 213 231 312 321, then 2 4 92 (the number of N-Queens solutions for boards of size 4, 6 and 8).
Common pitfalls
- Forgetting to copy:
out.append(path)stores a reference. Usepath[:]in Python or[...path]in JavaScript. - Forgetting to undo: every mutation before the recursive call needs an opposite after it (pop the item, clear the flag, remove from the set).
- Duplicates in the input: with repeated values you will produce repeated results. Sort first, and skip an option equal to the previous one at the same level (when that previous one was not used on this path).
- Pruning too late: checking validity only at the leaf throws away the main benefit. Check as soon as a choice is made.
- Exploding output: subsets and permutations grow exponentially and factorially. 20 items already mean over a million subsets; the algorithm is right, the problem is just big.
Practice
Generate balanced parentheses easy
Hint
You can add an open paren while you have some left, and a close paren only if it would not exceed the opens so far.
Show solution
Track opens and closes used. If opens < n, add (. If closes < opens, add ). When the string length is 2n, record it. The two conditions prune every invalid prefix, so you only ever build valid strings. The count is the Catalan number.
Combination sum medium
Hint
Pass a start index so you do not generate the same combination in a different order. Prune when the remaining target goes negative.
Show solution
For each call, loop i from start to n - 1. If candidates[i] > remaining, skip it (and break if the list is sorted). Otherwise append it, recurse with the same i (reuse allowed) and remaining - candidates[i], then pop. Record the path when remaining == 0.
Word search in a grid medium
Hint
Mark the current cell visited so you cannot reuse it, and unmark on the way back.
Show solution
For each starting cell, run DFS matching the word one character at a time. Temporarily replace the cell with a marker, try the four neighbours, then restore the cell. Return true as soon as the whole word is matched. Pruning on the first mismatched character keeps it fast; worst case is about cells * 3^len.
Sudoku solver hard
Hint
Pick the next empty cell, try digits 1 to 9 that fit row, column and box, and undo on failure. Which cell should you pick first?
Show solution
Keep sets for each row, column, and 3 by 3 box. For an empty cell, try every digit not present in its three sets; place it, recurse, and clear it if the recursion fails. Choosing the empty cell with the fewest legal digits first (a heuristic called most constrained variable) prunes dramatically more than scanning in order.
Interview questions
- How do you know a problem needs backtracking? It asks for all solutions, or for any solution under constraints, and the input is small (often
nup to about 20 or a small grid). - What is the difference between choosing, exploring, and unchoosing? Apply a decision to the shared state, recurse to handle the rest, then reverse the decision so siblings see the original state.
- How do you avoid duplicate results? Sort the input and skip an element equal to its predecessor at the same depth, or pass a start index for combinations.
- What is the time complexity of permutations?
O(n! * n):n!leaves and each copy costsn.
Interviewers look for: a clear skeleton, undoing state correctly, copying results, and proposing a pruning rule instead of brute-force checking at the leaves.
Quick check
In the subsets code, why do we append a copy of path instead of path itself?
Finished this lesson?
Further resources
- Backtracking (Wikipedia) (article)
- Eight queens puzzle (Wikipedia) (article)
- Python docs: itertools (docs)