What you will learn
- The choose / explore / un-choose template.
- Subsets, permutations and combinations, and how they differ.
- Pruning: cutting branches that can’t succeed.
Signals
- “All”, “every”, “generate”, “list all possible” (subsets, permutations, partitions, valid boards).
- Small constraints (n ≤ 10–20), because the output itself is exponential.
Template
def backtrack(state):
if is_complete(state):
record(copy_of(state))
return
for choice in choices(state):
if not valid(choice, state):
continue # prune
make(choice) # choose
backtrack(state) # explore
undo(choice) # un-choose
Code
"""Backtracking: choose, explore, un-choose."""
def subsets(nums):
out, path = [], []
def dfs(i):
if i == len(nums):
out.append(path[:])
return
path.append(nums[i]) # choose nums[i]
dfs(i + 1)
path.pop() # un-choose
dfs(i + 1) # skip nums[i]
dfs(0)
return out
def permutations(nums):
out, path, used = [], [], [False] * len(nums)
def dfs():
if len(path) == len(nums):
out.append(path[:])
return
for i, x in enumerate(nums):
if not used[i]:
used[i] = True
path.append(x)
dfs()
path.pop()
used[i] = False
dfs()
return out
def combination_sum(candidates, target):
out, path = [], []
candidates = sorted(candidates)
def dfs(start, remaining):
if remaining == 0:
out.append(path[:])
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining:
break # prune: sorted, so every later candidate is too big as well
path.append(c)
dfs(i, remaining - c) # i, not i + 1: a number may be reused
path.pop()
dfs(0, target)
return out
def solve_n_queens(n):
cols, diag, anti, count = set(), set(), set(), 0
def place(row):
nonlocal count
if row == n:
count += 1
return
for c in range(n):
if c in cols or row - c in diag or row + c in anti:
continue
cols.add(c); diag.add(row - c); anti.add(row + c)
place(row + 1)
cols.remove(c); diag.remove(row - c); anti.remove(row + c)
place(0)
return count
if __name__ == "__main__":
print(subsets([1, 2, 3]))
print(len(permutations([1, 2, 3, 4])), permutations([1, 2, 3])[:3])
print(combination_sum([2, 3, 6, 7], 7))
print([solve_n_queens(n) for n in range(4, 9)])
Output:
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
24 [[1, 2, 3], [1, 3, 2], [2, 1, 3]]
[[2, 2, 3], [7]]
[2, 10, 4, 40, 92]
- Subsets: at each index, two branches: include or skip. 2ⁿ results.
- Permutations: any unused element can go next; a
usedarray tracks what’s taken. n! results. - Combination sum: start each loop at
i(noti + 1) so numbers can repeat, and start fromstartso the same combination isn’t produced in different orders. Sorting enables thebreakprune. - N-Queens: three sets record attacked columns and diagonals (
row - candrow + care constant along each diagonal), making each validity check O(1). Counts for n = 4..8 are 2, 10, 4, 40, 92.
path[:] copies the path when recording. Appending path itself would record a reference that keeps changing, a very common bug.
Handling duplicates
When the input has duplicates (Subsets II, Permutations II), sort first and skip a choice equal to the previous one at the same depth: if i > start and nums[i] == nums[i-1]: continue.
Practise: backtracking problems.
Key takeaways
- Backtracking = choose, explore, un-choose, with pruning before recursing.
- Subsets branch include/skip; permutations pick any unused element; combinations move a start index forward.
- Record copies of the path, not the path itself.
- Sort to enable pruning and duplicate skipping.
Exercises
- Subsets II: subsets of a list with duplicates, without duplicate subsets.
- Word search in a grid (mark visited cells, restore on backtrack).
- Palindrome partitioning: all ways to split a string into palindromes.
Quiz
- Why does
combination_sumrecurse withiinstead ofi + 1? - What goes wrong if you
out.append(path)instead ofpath[:]? - How does N-Queens check diagonals in O(1)?
Show answers
- Each candidate can be used unlimited times, so the same index stays available.
- All recorded entries are the same list object, which ends up empty after backtracking finishes.
- All cells on one diagonal share
row - col, and on an anti-diagonal sharerow + col; sets of those values make the check O(1).