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] = []
trail: list = []
def explore(state) -> None:
if is_complete(state):
results.append(list(trail)) # COPY, always
return
for option in candidates(state):
if not is_valid(option, state):
continue # prune this branch entirely
trail.append(option) # choose
apply_to(state, option)
explore(advance(state, option)) # recurse
undo_from(state, option) # un-choose
trail.pop()
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 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]] = []
trail: list[int] = []
def build(start: int) -> None:
# Every node in the tree is a complete answer, so record on entry.
results.append(list(trail))
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)
return results
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.
"""
results: list[list[int]] = [[]]
for value in nums:
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 [
[nums[i] for i in range(n) if mask >> i & 1]
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]] = []
trail: list[int] = []
def build(start: int) -> None:
results.append(list(trail))
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.
if i > start and nums[i] == nums[i - 1]:
continue
trail.append(nums[i])
build(i + 1)
trail.pop()
build(0)
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]] = []
trail: list[int] = []
used = [False] * len(nums)
def build() -> None:
if len(trail) == len(nums):
results.append(list(trail))
return
for i, value in enumerate(nums):
if used[i]:
continue # already placed in this arrangement
used[i] = True # choose
trail.append(value)
build()
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]] = []
def build(first: int) -> None:
if first == len(nums):
results.append(list(nums))
return
for i in range(first, len(nums)):
nums[first], nums[i] = nums[i], nums[first] # choose
build(first + 1)
nums[first], nums[i] = nums[i], nums[first] # un-choose
build(0)
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.
def permute_unique(nums: list[int]) -> list[list[int]]:
"""Distinct permutations of a list that may contain repeats."""
nums.sort()
results: list[list[int]] = []
trail: list[int] = []
used = [False] * len(nums)
def build() -> None:
if len(trail) == len(nums):
results.append(list(trail))
return
for i, value in enumerate(nums):
if used[i]:
continue
# 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.
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
trail.append(value)
build()
trail.pop()
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]] = []
trail: list[int] = []
def build(start: int, remaining: int) -> None:
if remaining == 0:
results.append(list(trail))
return
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)
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.
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()
results: list[list[int]] = []
trail: list[int] = []
def build(start: int, remaining: int) -> None:
if remaining == 0:
results.append(list(trail))
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break
if i > start and candidates[i] == candidates[i - 1]:
continue # same value, same level
trail.append(candidates[i])
build(i + 1, remaining - candidates[i]) # i + 1: no reuse
trail.pop()
build(0, target)
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]] = []
queen_col: list[int] = [] # queen_col[row] is that row's column
cols: set[int] = set()
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."""
return ["." * c + "Q" + "." * (n - c - 1) for c in queen_col]
def place(row: int) -> None:
if row == n:
results.append(render())
return
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)
queen_col.append(col)
place(row + 1)
queen_col.pop() # un-choose, all four structures
anti_diagonals.remove(row + col)
diagonals.remove(row - col)
cols.remove(col)
place(0)
return results
def total_n_queens(n: int) -> int:
"""N-Queens II: just how many solutions, no boards."""
cols: set[int] = set()
diagonals: set[int] = set()
anti_diagonals: set[int] = set()
def place(row: int) -> int:
if row == n:
return 1
count = 0
for col in range(n):
if col in cols or (row - col) in diagonals or (row + col) in anti_diagonals:
continue
cols.add(col)
diagonals.add(row - col)
anti_diagonals.add(row + col)
count += place(row + 1)
anti_diagonals.remove(row + col)
diagonals.remove(row - col)
cols.remove(col)
return count
return place(0)
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.