A search that never looks at most of the possibilities: the moment a partial answer breaks a rule, it throws away every solution that would have grown from it.
A search that never looks at most of the possibilities: the moment a partial answer breaks a rule, it throws away every solution that would have grown from it.
Place 8 queens on a chessboard so that none of them attack each other. There are 4,426,165,368 ways to choose 8 squares out of 64, and exactly 92 of them work. Checking four billion boards is hopeless, but almost every bad board goes bad early: put two queens in the same column and nothing you do with the remaining six can save it. Backtracking cashes in on that observation. It builds a solution one choice at a time and abandons the attempt the moment a partial solution breaks a rule, undoing the last choice and trying the next option instead.
The name sounds like a standalone algorithm, but backtracking is really just recursion running three moves in a loop: choose, explore, undo. That makes it brute force with two upgrades, a prune that kills doomed branches early and an undo that keeps shared state honest, and those two upgrades are enough to enumerate every subset, every permutation, and every valid Sudoku board without writing a single nested loop.
Every backtracking algorithm walks a tree that never actually gets built. Each node is a partial solution, each edge is one choice, and the walk is depth-first: commit to a choice, explore everything that follows from it, then undo it and take the next branch. Watch the walk generate every subset of [1, 2, 3], where each level may only choose elements to the right of the last choice and every node gets recorded. The first dive commits 1, then 2, then 3, recording [], [1], [1, 2], and [1, 2, 3] on the way down. Now the walk sits at the bottom with nothing left to choose. Predict before reading on: which subset gets recorded next?
The walk undoes the 3, undoes the 2, and from [1] chooses the 3 directly, recording [1, 3]. That backing up is the move the whole technique is named after. The full recording order runs [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3], which is 8 subsets for 3 elements, and the count doubles with every element added: 20 elements means 1,048,576 subsets. No algorithm beats O(2ⁿ) here, because the output alone is that large.
The picture most people carry is a maze walker dropping breadcrumbs: stride forward until a dead end, follow the crumbs back to the last junction, take the other corridor. Keep the picture, but know where it lies. In code there is only one trail of breadcrumbs, a single shared path that every branch mutates and repairs, and that one detail is where nearly all backtracking bugs come from.
Subsets never look left, because choosing 2 and then 1 would rebuild the same subset as 1 then 2. Permutations are the opposite case: order is the whole point, so every element not already in the path is a legal next choice, and the bookkeeping changes from a start index into a used array. Run it on [1, 2, 3] and the six permutations arrive in dictionary order: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].
The tree now has n! leaves, and factorials grow meaner than powers of two: 3! = 6 is cute, 10! = 3,628,800 is not. The rule of thumb worth keeping: a start index means order doesn't matter (subsets, combinations), a used array means it does (permutations).
You might think recording a finished solution is the safe part: the path is complete, append it to the results, move on. Append the path itself, though, and the recursion that follows keeps mutating the very object you stored, because lists travel by reference in Python, Java, and JavaScript alike. When everything unwinds, your result holds eight pointers to the same empty list. The fix costs one character in Python: result.append(path[:]) stores a snapshot instead of the trail.
The second bug is quieter. Forget the undo after a recursive call and nothing crashes. The path just carries leftovers from one branch into the next, and the output is wrong in ways that look almost right. Delete the pops from the subsets code above and the first four results come out correct, then the path stops shrinking: the fifth "subset" is [1, 2, 3, 3] and the last is [1, 2, 3, 3, 2, 3, 3]. Silent corruption like that is why the undo line gets written in the same breath as the recursive call.
Left alone, a state tree is exponential, and pruning is what makes that livable. Back to the queens: placing one queen per row gives 8⁸ = 16,777,216 ways to fill a board row by row. Check the no-attack constraint at every row instead of at the bottom, and entire subtrees die the moment two queens clash. A pruning solver visits on the order of 15,000 nodes on its way to all 92 solutions. The prune didn't change the worst case. It changed the tree that actually grows.
Generate Parentheses shows the same effect on strings. Of the 256 strings you can write with eight parentheses, only 14 are balanced. Add an opener only while one remains and a closer only when it would close something, and the walk constructs the 14 without ever touching the other 242. Pruning has one failure mode worth fearing, though: a condition that's slightly too strong silently deletes valid answers. Test every prune against a case small enough to enumerate by hand.
used[i]. The mutation is cheap precisely because it's shared: every level of the recursion sees the same path object.path[:] in Python or new ArrayList<>(path) in Java. The path itself keeps changing after you leave.Backtracking problems split into two families. Enumeration problems want every subset, combination, or permutation, and the setup is always the same three blanks: the choices at each step, the constraint that invalidates a choice, and the shape of a finished solution. Combination Sum fills them in as: choices are the candidates from the start index onward (passing i instead of i + 1 lets a candidate repeat), the constraint is that a candidate can't exceed the remaining target, and the goal is a remaining target of exactly 0.
Constraint-satisfaction problems, N-Queens, Sudoku, Word Search, run the same loop but hunt for valid configurations instead of listing combinations. The choice is a column, a digit, or a direction, and the validity check in front of each recursive call is where all the intelligence lives. One special case earns its own line: duplicates. Generating subsets of [1, 2, 2] naively produces [1, 2] twice. Sort first, then let only the first copy of equal values branch at any given tree level, and the duplicates never get built at all.
Backtracking rewards habits more than memorization. Five that pay off:
Two questions before the problems. Why does appending path instead of path[:] leave you with a result full of identical lists, and which piece of bookkeeping, the start index or the used array, belongs to permutations? If both answers come easily, the mechanism is yours. The problems below run the enumeration trio first, then the duplicate variants, then the constraint solvers where pruning does the heavy lifting:
Completed | Title | Status | Notes | Solution | |
|---|---|---|---|---|---|
subsets.py
def subsets(nums: list[int]) -> list[list[int]]:
result = []
path = []
def dfs(start: int) -> None:
# Every node in the tree is a valid subset
result.append(path[:])
for i in range(start, len(nums)):
# Choose: commit nums[i] to the path
path.append(nums[i])
# Explore: everything that can follow nums[i]
dfs(i + 1)
# Undo: hand the next branch a clean path
path.pop()
dfs(0)
return resultpermutations.py
def permutations(nums: list[int]) -> list[list[int]]:
result = []
path = []
used = [False] * len(nums)
def dfs() -> None:
# A full-length path is a finished permutation
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
# Skip elements already placed in the path
if used[i]:
continue
# Choose: place nums[i] in the next slot
path.append(nums[i])
used[i] = True
# Explore: fill the remaining slots
dfs()
# Undo: free nums[i] for other branches
path.pop()
used[i] = False
dfs()
return result