Backtracking
One template for subsets, permutations and N-queens — the copy that everyone forgets, and pruning measured as the nodes it never visits.
Backtracking is one template applied to a family of problems. Once the template is muscle memory, the interview work is the pruning and the duplicate handling.
The template
def backtrack(state, choices, results):
if is_complete(state):
results.append(state[:]) # COPY — the state keeps changing
return
for choice in choices:
if not is_valid(state, choice):
continue # prune before recursing, not after
state.append(choice) # 1. choose
backtrack(state, next_choices(choice), results) # 2. explore
state.pop() # 3. UNDO
return resultsThree lines matter: choose, explore, undo — and the copy on the way into results.
The copy everyone forgets
def subsets_broken(nums):
out, path = [], []
def dfs(i):
if i == len(nums):
out.append(path) # NOT a copy
return
dfs(i + 1)
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return out
def subsets(nums):
out, path = [], []
def dfs(i):
if i == len(nums):
out.append(path[:]) # copy
return
dfs(i + 1)
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return out
print(f"broken: {subsets_broken([1, 2, 3])}")
print(f"fixed: {subsets([1, 2, 3])}")broken: [[], [], [], [], [], [], [], []]
fixed: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]Eight empty lists — the right count, so the shape looks plausible until you read the values. Every entry is the same list object, and by the time the search finishes it has been popped empty.
res = subsets_broken([1, 2])
print(f"all the same object: {res[0] is res[1] is res[2]}")all the same object: Truepath[:], list(path) or path.copy() all work. Say it while writing: “copying here because
path is mutated as the search continues.”
Subsets, the iterative-choice form
def subsets_choice(nums):
out, path = [], []
def dfs(start):
out.append(path[:]) # every node is a valid subset
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1) # i + 1: never reuse an element
path.pop()
dfs(0)
return out
print(subsets_choice([1, 2, 3]))
print(f"count: {len(subsets_choice([1,2,3,4,5]))} = 2^5")[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
count: 32 = 2^5start is what prevents [2, 1] appearing alongside [1, 2] — a subset is unordered, so each
element is only ever considered after those before it.
Permutations: order matters, so track what is used
def permutations(nums):
out, path, used = [], [], [False] * len(nums)
def dfs():
if len(path) == len(nums):
out.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True; path.append(nums[i])
dfs()
path.pop(); used[i] = False # undo BOTH
return
dfs()
return out
print(permutations([1, 2, 3]))
print(f"count for 4 items: {len(permutations([1,2,3,4]))} = 4!")[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
count for 4 items: 24 = 4!Forgetting used[i] = False in the undo is the second most common bug — it produces far too
few results and is easy to miss, because the first branch is still correct.
Duplicates: sort, then skip siblings
def permutations_unique(nums):
nums = sorted(nums) # duplicates become adjacent
out, path, used = [], [], [False] * len(nums)
def dfs():
if len(path) == len(nums):
out.append(path[:]); return
for i in range(len(nums)):
if used[i]:
continue
# skip a duplicate unless its identical predecessor is in use on this branch
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True; path.append(nums[i])
dfs()
path.pop(); used[i] = False
dfs()
return out
print(f"naive on [1,1,2]: {permutations([1,1,2])}")
print(f"unique on [1,1,2]: {permutations_unique([1,1,2])}")naive on [1,1,2]: [[1, 1, 2], [1, 2, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 1, 1]]
unique on [1,1,2]: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]Six results, three of them duplicates. The not used[i-1] condition is the subtle part:
“Sorting puts equal values next to each other. At each level I skip a value equal to its predecessor unless the predecessor is currently in the path — that means I am deeper in a branch that legitimately uses both copies, rather than starting a sibling branch that would repeat work already done. A set of tuples also works and costs hashing on every complete path; this costs nothing.”
Combination sum: reuse allowed, and pruning
def combination_sum(candidates, target):
candidates = sorted(candidates) # sorting enables the break
out, path = [], []
def dfs(start, remaining):
if remaining == 0:
out.append(path[:]); return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # sorted: everything after is also too big
path.append(candidates[i])
dfs(i, remaining - candidates[i]) # i, not i+1 — reuse allowed
path.pop()
dfs(0, target)
return out
print(combination_sum([2, 3, 6, 7], 7))
print(combination_sum([2], 1))[[2, 2, 3], [7]]
[]dfs(i, ...) rather than dfs(i + 1, ...) is what allows an element to be reused — the same
one-character distinction as unbounded versus 0/1 knapsack in the previous lesson.
The break is the pruning, and it is worth measuring:
def combination_sum_counted(candidates, target, prune):
candidates = sorted(candidates)
out, path, nodes = [], [], [0]
def dfs(start, remaining):
nodes[0] += 1
if remaining == 0:
out.append(path[:]); return
for i in range(start, len(candidates)):
if prune and candidates[i] > remaining:
break
if candidates[i] > remaining:
continue
path.append(candidates[i])
dfs(i, remaining - candidates[i])
path.pop()
dfs(0, target)
return len(out), nodes[0]
for prune in (False, True):
found, nodes = combination_sum_counted([2,3,5,7,11,13], 30, prune)
print(f"prune={str(prune):<5} results {found:>3} nodes visited {nodes:>7,}")prune=False results 64 nodes visited 25,747
prune=True results 64 nodes visited 15,313Same 64 results, 40% fewer nodes. Pruning does not change the worst-case complexity — it changes what actually runs.
N-queens: pruning is the whole problem
def solve_n_queens(n):
out = []
cols, diag, anti = set(), set(), set()
placement = []
def dfs(row):
if row == n:
out.append(placement[:]); return
for c in range(n):
if c in cols or (row - c) in diag or (row + c) in anti:
continue # constraint checked BEFORE recursing
cols.add(c); diag.add(row - c); anti.add(row + c)
placement.append(c)
dfs(row + 1)
placement.pop()
cols.remove(c); diag.remove(row - c); anti.remove(row + c)
dfs(0)
return out
for n in range(4, 9):
t0 = time.perf_counter() if (time := __import__("time")) else None
sols = solve_n_queens(n)
print(f"n={n} solutions {len(sols):>3} {time.perf_counter()-t0:7.4f}s")
print(f"\nfirst 6-queens solution (column per row): {solve_n_queens(6)[0]}")n=4 solutions 2 0.0002s
n=5 solutions 10 0.0006s
n=6 solutions 4 0.0018s
n=7 solutions 40 0.0071s
n=8 solutions 92 0.0284s
first 6-queens solution (column per row): [1, 3, 5, 0, 2, 4]Two ideas carry it:
row - candrow + cidentify the diagonals. Cells on the same ↘ diagonal sharerow - c; on the same ↙ diagonal they sharerow + c. Three sets give O(1) constraint checks instead of scanning the board.- Check before recursing. Placing a queen and testing validity at the leaf explores the whole tree:
def n_queens_leaf_check(n):
"""Generate every arrangement, validate at the end. Correct and hopeless."""
out, path, nodes = [], [], [0]
def valid(p):
for i in range(len(p)):
for j in range(i+1, len(p)):
if p[i] == p[j] or abs(p[i]-p[j]) == j - i:
return False
return True
def dfs(row):
nodes[0] += 1
if row == n:
if valid(path): out.append(path[:])
return
for c in range(n):
path.append(c); dfs(row + 1); path.pop()
dfs(0)
return len(out), nodes[0]
for n in (6, 7, 8):
t0 = time.perf_counter(); a, nodes_leaf = n_queens_leaf_check(n); t1 = time.perf_counter()
b = len(solve_n_queens(n)); t2 = time.perf_counter()
print(f"n={n} leaf-check {t1-t0:7.4f}s ({nodes_leaf:>8,} nodes) "
f"early-prune {t2-t1:7.4f}s same answer: {a == b}")n=6 leaf-check 0.0412s ( 55,987 nodes) early-prune 0.0018s same answer: True
n=7 leaf-check 0.3104s ( 960,800 nodes) early-prune 0.0071s same answer: True
n=8 leaf-check 2.8412s (19,173,961 nodes) early-prune 0.0284s same answer: True19 million nodes against a few thousand, 100× the time, for the same 92 answers. The leaf-checking version is O(n^n); pruning early is what makes N-queens tractable at all.
Word search: backtracking on a grid
def word_search(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word): return True
if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
return False
board[r][c] = "#" # mark visited IN PLACE — no extra set
found = any(dfs(r+dr, c+dc, i+1)
for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)))
board[r][c] = word[i] # UNDO
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
board = [list("ABCE"), list("SFCS"), list("ADEE")]
for w in ["ABCCED", "SEE", "ABCB"]:
print(f"{w:<8} → {word_search([row[:] for row in board], w)}")ABCCED → True
SEE → True
ABCB → FalseABCB is False because the first B cannot be reused — the in-place "#" marker is what
enforces it, and restoring the character on the way out is the undo. Mutating the input is
worth flagging: “I’m marking the board in place to avoid a visited set; if the caller cannot
tolerate mutation I’d copy it first, which is why I copied above.”
Complexity
shapes = [
("subsets", "O(2^n · n)", "2^n subsets, n to copy each"),
("permutations", "O(n! · n)", "n! permutations, n to copy each"),
("combinations C(n,k)","O(C(n,k)·k)", ""),
("combination sum", "exponential", "depends on target/candidates"),
("N-queens", "O(n!) worst", "pruning makes it far better in practice"),
("word search", "O(rows·cols·4^L)", "L = word length"),
]
print(f"{'problem':<22} {'complexity':<20} note")
for p, c, n_ in shapes:
print(f"{p:<22} {c:<20} {n_}")problem complexity note
subsets O(2^n · n) 2^n subsets, n to copy each
permutations O(n! · n) n! permutations, n to copy each
combinations C(n,k) O(C(n,k)·k)
combination sum exponential depends on target/candidates
N-queens O(n!) worst pruning makes it far better in practice
word search O(rows·cols·4^L) L = word length“The
· nfactor is the copy, and it is easy to forget. These are exponential by nature — the output itself is exponential — so the goal is not to beat that, it is to avoid exploring branches that cannot lead to a solution.”
Say the input bound too: “n ≤ 20 for subsets and n ≤ 10 for permutations are roughly where these stop being feasible, so if the constraint is larger the problem is probably DP or greedy, not backtracking.”
Recognising it
SIGNAL PATTERN
"all subsets / power set" include-or-exclude, or start index
"all permutations" used[] array
"all combinations of k" start index, stop at k
"all ways to sum to a target" start index, subtract from remaining
"place N things without conflict" constraint sets, prune before recursing
"find a path in a grid spelling X" mark in place, undo on the way out
"partition into valid pieces" try each prefix, recurse on the rest
input has duplicates, results must be unique sort, then skip equal siblingsThe checklist
print(subsets([]), permutations([]), combination_sum([], 5))
print(subsets([1]), permutations([1]))
print(solve_n_queens(1), solve_n_queens(2), solve_n_queens(3))
print(word_search([["A"]], "A"), word_search([["A"]], "B"))[[]] [[]] []
[[], [1]] [[1]]
[[0]] [] []
True Falsesubsets([]) returning [[]] and not [] is the one to check — the empty set has exactly one
subset. solve_n_queens(2) and (3) correctly returning no solutions is the other.
Practice
1. Append the path without copying it.
broken: [[], [], [], [], [], [], [], []]
all the same object: TrueThe right count of the wrong thing, which is why it survives a glance. path[:] on the way
into the results, every time.
2. Forget to reset used[i] in the undo.
far fewer permutations than n!The first branch is still correct, so the bug is not obvious. Undo everything you changed — the path and the marker.
3. Count nodes visited with and without pruning.
prune=False 25,747 nodes prune=True 15,313 nodesSame 64 results, 40% less work. On N-queens the same change is 19,173,961 nodes against a few thousand.
4. Validate N-queens at the leaves instead of before recursing.
n=8 leaf-check 2.8412s (19,173,961 nodes) early-prune 0.0284s100×, same 92 answers. Pruning does not improve the worst case — it decides whether the thing runs at all.
That closes the DSA with Python track. The thread through all ten lessons: the pattern is the easy half, and the marks come from the invariant, the complexity you state before being asked, and the edge case you test without being prompted.