Build a candidate one choice at a time. When it cannot lead anywhere, undo the last choice and try the next. The undo is the whole pattern.
Backtracking is depth-first search over a tree of decisions rather than a tree of nodes. The output is exponential by nature, so the goal is never to avoid the exponential; it is to cut off whole branches as early as possible, and to enumerate each answer exactly once.
| Signal | What it looks like |
|---|---|
| “All” plus a structure | “all subsets”, “every permutation”, “all valid parentheses”, “every path”. |
| Constraint satisfaction | N-Queens, Sudoku, word search, graph colouring. Place things without conflict. |
| Tiny input bound | n ≤ 20 for subsets, n ≤ 10 for permutations. A small bound is a hint that exponential is expected. |
| “Does any arrangement exist” | Same search, but return as soon as one is found. |
Before writing any backtracking code, answer these three out loud. They determine every line.
| Question | What it decides |
|---|---|
| 1. What is one choice? | What the for loop iterates over: an index, a value, a column, a letter. |
| 2. When do I record an answer? | At every node (subsets), or only at leaves (permutations, N-Queens), or only when a condition holds (combination sum). |
| 3. How do I avoid duplicates? | A start index for combinations, a used array for permutations, and a skip rule if the input itself has repeats. |
[1, 2] and [2, 1] are the same answer, and a start index enforces one canonical ordering. Permutations are ordered, so both are wanted, and instead you need a used marker so no element is picked twice within one arrangement. Choosing the wrong guard gives you either duplicates or missing answers.| Problem | Answers | Time | Why |
|---|---|---|---|
| Subsets | 2ⁿ | O(n · 2ⁿ) | Each of 2ⁿ subsets is copied, at O(n) each. |
| Permutations | n! | O(n · n!) | Same reasoning. |
| Combination Sum | varies | O(nt/m) | Depth is bounded by target / smallest candidate. |
| N-Queens | varies | O(n!) | Upper bound. Pruning makes the real count far smaller. |
n. Interviewers ask about it, and “there are 2ⁿ answers and copying each one costs O(n)” is the whole explanation.def backtrack_all(options) -> list[list]:
"""Enumerate every valid arrangement."""
results: list[list] = [] # every finished answer, each its own copy
trail: list = [] # the choices made on the current path, root to here
def explore(state) -> None:
# is_complete(state): is the trail a finished answer?
# Permutations: len(trail) == len(nums). Combination Sum: remaining == 0.
# Subsets: always true, so record on entry and do NOT return.
if is_complete(state):
# list(trail) copies. trail keeps changing, so a bare append
# would leave every result pointing at one list, empty at the end.
results.append(list(trail))
return
# candidates(state): the options for the next decision.
# Subsets: nums[start:]. Permutations: all of nums. N-Queens: columns 0..n-1.
# Invariant: trail and state are exactly as they were on entry.
for option in candidates(state):
# is_valid(option, state): may this option be taken here?
# Permutations: not used[i]. N-Queens: the square is not attacked.
if not is_valid(option, state):
continue # prune this branch entirely
trail.append(option) # choose
# apply_to: record the choice in any side structures.
# Permutations: used[i] = True. N-Queens: add to the three sets.
apply_to(state, option)
# advance(state, option): the state one level deeper.
# Subsets: start becomes i + 1. Combination Sum: remaining drops by option.
explore(advance(state, option)) # recurse
# undo_from: exact reverse of apply_to, so the loop invariant holds.
undo_from(state, option) # un-choose
trail.pop() # drop the option we just tried
# initial_state: the root of the tree, nothing chosen yet.
# Subsets: start = 0. Combination Sum: start 0, remaining = target.
# N-Queens: row 0.
explore(initial_state)
return results
Every problem below is this skeleton with different answers to the three questions. The continue is where pruning lives, and pruning is the only lever you have on the running time.
trail list. Choose pushes, un-choose pops, so the list always matches the current path.Reading the figure. Each column is a moment in time, left to right. Blue boxes sit in trail. Amber is the value just pushed. The red dashed box is the value just popped. Notice that frame 4 matches frame 2 exactly. That is the undo restoring the state before the next option.
trail instead of list(trail). Every result ends up being the same list object, empty at the end. The number one bug in this pattern.start = i + 1 when reuse is allowed, or start = i when it is not. One character, completely different problem.n. Mutate and undo instead.Given an array of distinct integers, return all possible subsets, the power set. The answer must not contain duplicate subsets.
start index. By only ever extending with a later index, each subset is generated in exactly one order.def subsets(nums: list[int]) -> list[list[int]]:
"""Every subset of a list of distinct integers.
Args:
nums: Distinct integers.
Returns:
All 2**len(nums) subsets, including the empty one.
Example:
>>> subsets([1, 2, 3])
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
"""
results: list[list[int]] = [] # every subset found so far
trail: list[int] = [] # the subset being built on this path
# start: the first index this level may pick. Only later indices are
# allowed, so each subset is built in one order: increasing index.
def build(start: int) -> None:
# Every node in the tree is a complete answer, so record on entry.
# list(trail) copies, because trail keeps changing after this.
results.append(list(trail))
# i: the index added at this level. Invariant: trail is the same
# at the top of every pass, because each pass undoes its own choice.
for i in range(start, len(nums)):
trail.append(nums[i]) # choose
build(i + 1) # i + 1: never reuse or go backwards
trail.pop() # un-choose
build(0) # 0: the root may pick any index
return results
subsets([1, 2, 3]) records a subset on every call, so the output order is the depth-first visit order.Reading the figure. Each box is one call to build, and #1 to #8 is the order it records. Height is len(trail). A solid blue step is one push. A red dashed step pops twice, then pushes the next index. The list matches the doctest exactly: [ ], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3].
def subsets_iterative(nums: list[int]) -> list[list[int]]:
"""Double the answer set for each new element.
Adding an element to a power set gives every old subset, plus every old
subset with the new element appended. That doubling is why there are 2**n.
"""
# [[]]: the power set of nothing holds one subset, the empty one.
results: list[list[int]] = [[]]
# Invariant: results is the power set of the values seen so far.
for value in nums:
# The comprehension reads the old results only, then += appends.
# So the count doubles: old subsets, plus each one with value added.
results += [subset + [value] for subset in results]
return results
Two lines, and it makes the 2ⁿ count obvious. Show the backtracking version first, because the interviewer wants to see the pattern, then offer this.
def subsets_bitmask(nums: list[int]) -> list[list[int]]:
"""Each integer from 0 to 2**n - 1 is a membership mask."""
n = len(nums)
return [
# mask >> i & 1: shift bit i to the bottom, keep only that bit.
# 1 means nums[i] is in this subset, 0 means it is out.
[nums[i] for i in range(n) if mask >> i & 1]
# 1 << n is 2**n, so mask runs 0..2**n - 1: one mask per subset.
for mask in range(1 << n)
]
def subsets_with_dup(nums: list[int]) -> list[list[int]]:
"""Subsets of a list that may contain repeated values, no duplicate subsets."""
nums.sort() # equal values must be adjacent
results: list[list[int]] = [] # every distinct subset found so far
trail: list[int] = [] # the subset being built on this path
def build(start: int) -> None:
results.append(list(trail)) # every node is an answer, so copy it now
# i: the index added at this level. Invariant: trail is unchanged
# at the top of every pass.
for i in range(start, len(nums)):
# Skip a repeat at the same tree level. The first copy already
# generated every subset this branch could produce.
# i > start: not the first option at this level.
# i - 1: the neighbour to the left, equal values sit side by side.
if i > start and nums[i] == nums[i - 1]:
continue
trail.append(nums[i]) # choose
build(i + 1) # i + 1: only later indices, no reuse
trail.pop() # un-choose
build(0) # 0: the root may pick any index
return results
i > start and not i > 0. The rule is “do not pick the same value twice as the same decision”. Picking a repeated value at a deeper level is legitimate, that is how [2, 2] gets built. i > start says “this is not the first option I am trying at this level”, which is exactly the right condition. This idiom reappears in every duplicate-tolerant backtracking problem.[[]], a list containing the empty subset, not an empty list.[[], [x]].n = 20 gives about a million subsets, which is fine. n = 30 gives a billion, which is not. Say where the ceiling is.start index is what makes each subset appear exactly once.”Given an array of distinct integers, return all possible permutations.
start index.used array, because the constraint is “each element once per arrangement”, not “increasing order”. Order matters here, so a start index would wrongly discard most answers.def permute(nums: list[int]) -> list[list[int]]:
"""Every ordering of a list of distinct integers.
Args:
nums: Distinct integers.
Returns:
All len(nums)! permutations.
Example:
>>> permute([1, 2, 3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
"""
results: list[list[int]] = [] # every full arrangement found
trail: list[int] = [] # the arrangement built so far
used = [False] * len(nums) # used[i]: nums[i] is in trail. All start free.
def build() -> None:
# Full length means every element is placed: one finished permutation.
if len(trail) == len(nums):
results.append(list(trail)) # copy, because trail keeps changing
return
# i: the candidate for the next position. Every index is tried, so no start.
# Invariant: trail and used are the same at the top of every pass.
for i, value in enumerate(nums):
if used[i]:
continue # already placed in this arrangement
used[i] = True # choose
trail.append(value)
build() # fill the remaining positions
trail.pop() # un-choose, both parts
used[i] = False
build()
return results
def permute_swap(nums: list[int]) -> list[list[int]]:
"""No used array: swap each candidate into position, then swap it back."""
results: list[list[int]] = [] # every arrangement found
# first: the position being filled. nums[:first] is fixed, nums[first:]
# holds the elements still free to go here.
def build(first: int) -> None:
# Every position is fixed, so nums itself is one permutation.
if first == len(nums):
results.append(list(nums)) # copy, because nums keeps changing
return
# i: which free element moves into position first.
# Invariant: nums is in the same order at the top of every pass.
for i in range(first, len(nums)):
nums[first], nums[i] = nums[i], nums[first] # choose
build(first + 1) # + 1: fill the next position
nums[first], nums[i] = nums[i], nums[first] # un-choose
build(0) # 0: start filling at the first position
return results
Uses O(1) extra space beyond the recursion, and it is a nice thing to show. The cost is that the output order is no longer lexicographic, so mention that if the problem cares.
For [1, 2, 3]: the first level tries 1, 2, 3. Inside the 1 branch, the second level tries 2 and 3, since 1 is marked used. Inside 1, 2 only 3 is free, so the trail reaches full length and [1, 2, 3] is recorded. Unwinding un-marks 3, then 2, and the 1 branch tries 3 next.
permute([1, 2, 3]). Every level may pick any unused value, so the tree fans out 3, then 2, then 1.Reading the figure. Blue boxes are partial trails, which are not recorded. Green boxes are full-length trails, the six answers. The amber path is the first one the walkthrough follows. The muted used labels show why the [1] branch offers only 2 and 3. Compare with Figure 10.1. There is no start index here, so [2,1] appears as well as [1,2].
def permute_unique(nums: list[int]) -> list[list[int]]:
"""Distinct permutations of a list that may contain repeats."""
nums.sort() # equal values must be adjacent
results: list[list[int]] = [] # every distinct arrangement found
trail: list[int] = [] # the arrangement built so far
used = [False] * len(nums) # used[i]: nums[i] is in trail. All start free.
def build() -> None:
if len(trail) == len(nums): # every element placed
results.append(list(trail)) # copy, because trail keeps changing
return
# i: the candidate for the next position.
# Invariant: trail and used are the same at the top of every pass.
for i, value in enumerate(nums):
if used[i]:
continue # already placed in this arrangement
# Among equal values, only ever use them left to right. If the
# previous copy is unused, this branch is a mirror of one we
# already explored.
# i > 0: index 0 has no left neighbour. i - 1: that left neighbour.
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True # choose
trail.append(value)
build() # fill the remaining positions
trail.pop() # un-choose, both parts
used[i] = False
build()
return results
not used[i - 1] is subtle. It forces equal values to be consumed in index order, so exactly one of the interchangeable orderings survives. Write out [1, 1, 2] by hand once and it becomes clear; it is a common follow-up.[[]].[[x]].n = 10 is 3.6 million permutations, about the practical limit. n = 12 is half a billion.itertools.permutations exists and is what you would ship. Say so after writing the manual version.start index here, because order matters and every position can draw from the whole array. The used array is what keeps each element to one appearance per arrangement.”Given an array of distinct positive integers candidates and a target, return all unique combinations that sum to the target. The same candidate may be used unlimited times. Two combinations are the same if they use the same multiset of numbers.
start index, but recursing with i rather than i + 1, because a candidate may be reused. That single character is the difference between this problem and Combination Sum II.candidates[i] > remaining, you can break rather than continue, because every later candidate is even larger and equally hopeless. That converts a per-item skip into cutting off the entire rest of the level, and it is the difference between a fast solution and a slow one on adversarial inputs.def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
"""All multisets of candidates summing exactly to target, with reuse.
Args:
candidates: Distinct positive integers. Sorted in place.
target: The required total, positive.
Returns:
Each qualifying combination once, in non-decreasing order.
Example:
>>> combination_sum([2, 3, 6, 7], 7)
[[2, 2, 3], [7]]
"""
candidates.sort() # required for the break-based pruning below
results: list[list[int]] = [] # every combination that hits the target
trail: list[int] = [] # the numbers chosen on this path
# start: the smallest index this level may pick, so trail stays
# non-decreasing. remaining: target minus sum(trail).
def build(start: int, remaining: int) -> None:
# 0 left means trail sums to exactly target: record a copy.
if remaining == 0:
results.append(list(trail))
return
# i: the candidate added at this level.
# Invariant: trail and remaining are unchanged at the top of every pass.
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # sorted, so every later candidate also overshoots
trail.append(candidates[i]) # choose
build(i, remaining - candidates[i]) # i, not i + 1: reuse is allowed
trail.pop() # un-choose
build(0, target) # 0: any candidate may start. Nothing spent yet.
return results
candidates = [2, 3, 6, 7], target = 7:
| trail | remaining | what happens |
|---|---|---|
| [2] | 5 | keep going from index 0 |
| [2, 2] | 3 | keep going |
| [2, 2, 2] | 1 | 2 > 1, break, dead end |
| [2, 2, 3] | 0 | record |
| [2, 3] | 2 | start is 1, so 2 is unavailable, dead end |
| [7] | 0 | record |
Note how [3, 2, 2] never appears: the start index prevents going back to a smaller candidate.
combination_sum([2, 3, 6, 7], 7) finds [2, 2, 3] and [7]. Sorting lets each dead level stop with one break.Reading the figure. Each box shows the trail and the remaining amount. Green boxes hit zero and are recorded. Red boxes are dead ends, and the red note says which test cut them off. Blue boxes keep searching. Children only use candidates at or after the parent’s index, so [3, 2, 2] is never built.
The recursion cannot go deeper than target / min(candidates), since each level subtracts at least the smallest candidate. That is the honest bound, and it explains why positivity is required.
def combination_sum_ii(candidates: list[int], target: int) -> list[list[int]]:
"""Each candidate may be used at most once, and the input may repeat."""
candidates.sort() # adjacent repeats, and lets the break below work
results: list[list[int]] = [] # every combination that hits the target
trail: list[int] = [] # the numbers chosen on this path
# start: the first index this level may pick. remaining: target minus sum(trail).
def build(start: int, remaining: int) -> None:
if remaining == 0: # exact hit: record a copy
results.append(list(trail))
return
# i: the candidate added at this level.
# Invariant: trail and remaining are unchanged at the top of every pass.
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # sorted: the rest overshoot too
# i > start: not the first option at this level.
# i - 1: the left neighbour, equal values sit side by side.
if i > start and candidates[i] == candidates[i - 1]:
continue # same value, same level
trail.append(candidates[i]) # choose
build(i + 1, remaining - candidates[i]) # i + 1: no reuse
trail.pop() # un-choose
build(0, target) # 0: any candidate may start. Nothing spent yet.
return results
Two changes from the first version: i + 1 instead of i, and the i > start duplicate skip. Being able to state both differences quickly is the point of studying them together.
[].remaining stops shrinking. Confirm the candidates are positive.target == 0: returns [[]]. Ask whether that is wanted.i rather than i + 1 is what allows reuse, and the start index is what stops the same multiset appearing in several orders. Sorting lets me break instead of continue.”Place n queens on an n × n board so that no two attack each other, and return every distinct solution as a list of board strings.
n. State this before writing anything; it is most of the insight.Scanning the board for conflicts is O(n) per placement. Three sets make it O(1):
| Attack line | Constant along it | Set |
|---|---|---|
| Column | col | cols |
| Diagonal, top-left to bottom-right | row - col | diagonals |
| Anti-diagonal, top-right to bottom-left | row + col | anti_diagonals |
Every square on a given diagonal has the same row - col, and every square on an anti-diagonal has the same row + col. So a placement conflicts exactly when one of its three keys is already in a set. Deriving those two identities on the whiteboard is what this question is really testing.
def solve_n_queens(n: int) -> list[list[str]]:
"""Every arrangement of n non-attacking queens on an n by n board.
Args:
n: Board size, n >= 1.
Returns:
Each solution as n strings of "." and "Q".
Example:
>>> solve_n_queens(4)
[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]
"""
results: list[list[str]] = [] # every finished board
queen_col: list[int] = [] # queen_col[row] is that row's column
cols: set[int] = set() # columns that already hold a queen
diagonals: set[int] = set() # keyed by row - col
anti_diagonals: set[int] = set() # keyed by row + col
def render() -> list[str]:
"""Turn the column-per-row list into the required board strings."""
# c dots, the queen, then the rest. n - c - 1: squares right of
# the queen, minus 1 for the queen's own square.
return ["." * c + "Q" + "." * (n - c - 1) for c in queen_col]
# row: the row to fill now. Rows 0..row-1 each hold one safe queen.
def place(row: int) -> None:
if row == n: # rows 0..n-1 all filled: a full solution
results.append(render())
return
# col: the column tried for this row, 0..n-1.
# Invariant: the three sets hold exactly the queens in rows 0..row-1.
for col in range(n):
# One queen per row is built in, so only columns and diagonals clash.
# row - col is constant on a down-right diagonal. row + col on an
# up-right one.
if col in cols or (row - col) in diagonals or (row + col) in anti_diagonals:
continue # prune: this square is attacked
cols.add(col) # choose
diagonals.add(row - col)
anti_diagonals.add(row + col)
queen_col.append(col)
place(row + 1) # + 1: move on to the next row
queen_col.pop() # un-choose, all four structures
anti_diagonals.remove(row + col)
diagonals.remove(row - col)
cols.remove(col)
place(0) # 0: start at the top row, board empty
return results
solve_n_queens(4) hits two dead ends, backs up to row 0, and then finds ['.Q..', '...Q', 'Q...', '..Q.'].Reading the figure. Each board is one moment, left to right. Blue squares are queens already placed. Amber is the newest queen. A red x is a square in the row being tried that the three sets reject. When a whole row is red, place returns and the caller un-chooses. Green queens in (d) form the first answer, queen_col = [1, 3, 0, 2].
def total_n_queens(n: int) -> int:
"""N-Queens II: just how many solutions, no boards."""
cols: set[int] = set() # columns that already hold a queen
diagonals: set[int] = set() # keyed by row - col
anti_diagonals: set[int] = set() # keyed by row + col
# row: the row to fill now. Returns how many ways rows row..n-1 can finish.
def place(row: int) -> int:
if row == n:
return 1 # all n rows filled: this path is 1 solution
count = 0 # solutions found below this row so far
# col: the column tried for this row, 0..n-1.
# Invariant: the three sets hold exactly the queens in rows 0..row-1.
for col in range(n):
if col in cols or (row - col) in diagonals or (row + col) in anti_diagonals:
continue # prune: this square is attacked
cols.add(col) # choose
diagonals.add(row - col)
anti_diagonals.add(row + col)
count += place(row + 1) # + 1: next row. Add its solution count.
anti_diagonals.remove(row + col) # un-choose, all three sets
diagonals.remove(row - col)
cols.remove(col)
return count
return place(0) # 0: start at the top row, board empty
Same search, no rendering and no trail. Faster in practice because it never builds strings.
The bound is loose. Row 0 has n choices, row 1 has at most n - 2 after pruning, and so on, so the real search is far smaller than n!. Solution counts: 2 for n = 4, 10 for n = 5, 92 for n = 8.
n = 1: one solution, ["Q"].n = 2 and n = 3: no solutions, returns []. A good correctness check.n = 8: 92 solutions, the classic.row - col and an anti-diagonal has constant row + col, so three sets give me O(1) conflict checks.”start index for combinations (order does not matter). used array for permutations (order does matter).build(i) allows reuse; build(i + 1) does not. One character.i > start and x[i] == x[i - 1].break on sorted data, is the only real lever on running time.Pattern 11, Modified Binary Search, is the opposite instinct. Instead of exploring everything, it throws half the possibilities away at every step, and the skill is spotting the monotone boundary that licenses the throw.