Backtracking & branch-and-bound
Backtracking is systematic brute force with a brain: build a solution incrementally, and the instant a partial choice cannot possibly lead to a valid answer, undo it and try the next option. It is how you generate subsets, permutations and combinations, solve N-queens and Sudoku, and search a grid for words. Branch-and-bound adds cost bounds to prune even harder on optimization problems. This lesson gives you the reusable template and the pruning mindset.
Learning objectives
- Write the universal backtracking template: choose → explore → un-choose.
- Generate subsets, permutations and combinations correctly (and dedupe).
- Solve N-queens and Sudoku with constraint-based pruning.
- Search a grid for a word (DFS with a visited mark you restore).
- Explain how pruning changes practical (not worst-case) complexity.
- Distinguish plain backtracking from branch-and-bound on optimization problems.
1 · The backtracking template advanced
Every backtracking algorithm is the same skeleton over a decision tree. At each node you choose an option, recurse to explore the consequences, then un-choose (undo the choice) so you can try the next option. A base case records a complete solution; a pruning check abandons hopeless branches early.
pythondef subsets(nums):
result, path = [], []
def backtrack(start):
result.append(path[:]) # record: every node is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1) # EXPLORE the rest
path.pop() # UN-CHOOSE (backtrack)
backtrack(0)
return result
print(subsets([1, 2, 3]))
print("count:", len(subsets([1, 2, 3])), "= 2^3")
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
count: 8 = 2^3path[:]) when recording a solution, never the live list. The path keeps mutating as you backtrack, so storing the reference gives you a list of identical (empty) lists at the end. And always pop() exactly what you append()ed — choose and un-choose must be mirror images.2 · Permutations & combinations intermediate
Same template, different branching. Combinations pick k of n ignoring order — pass a start index so you never look back. Permutations care about order — track which elements are already used. Counts: C(n,k) combinations, n! permutations, so these are exponential/factorial by nature.
pythondef combinations(n, k):
result, path = [], []
def backtrack(start):
if len(path) == k:
result.append(path[:]); return
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1) # i+1: never reuse -> no order duplicates
path.pop()
backtrack(1)
return result
def permutations(nums):
result, path, used = [], [], [False] * len(nums)
def backtrack():
if len(path) == len(nums):
result.append(path[:]); return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True; path.append(nums[i])
backtrack()
path.pop(); used[i] = False
backtrack()
return result
print("C(4,2):", combinations(4, 2))
print("perms of [1,2,3]:", permutations([1, 2, 3]))
print("counts:", len(combinations(4, 2)), len(permutations([1, 2, 3])))
C(4,2): [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
perms of [1,2,3]: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
counts: 6 6[1,1,2]), sort first and skip a value at the same tree level if it equals the previous one (if i>start and nums[i]==nums[i-1]: continue). That skip is what keeps [1,1,2] from producing the same subset/permutation twice.3 · N-queens — pruning by constraint advanced
Place N queens on an N×N board so none attack another. Backtracking places one queen per row; before placing in a column it checks the column and both diagonals are free. The pruning is brutal: a placement that conflicts kills that entire subtree immediately, so we explore vastly fewer than the N^N naive placements.
pythondef count_n_queens(n):
cols = set(); diag = set(); anti = set() # occupied columns / diagonals
count = 0
def backtrack(row):
nonlocal count
if row == n:
count += 1; return
for col in range(n):
if col in cols or (row - col) in diag or (row + col) in anti:
continue # PRUNE: conflict, skip this branch
cols.add(col); diag.add(row - col); anti.add(row + col) # CHOOSE
backtrack(row + 1) # EXPLORE
cols.discard(col); diag.discard(row - col); anti.discard(row + col) # UNDO
backtrack(0)
return count
for n in range(1, 9):
print(f"N={n}: {count_n_queens(n)} solutions")
N=1: 1 solutions
N=2: 0 solutions
N=3: 0 solutions
N=4: 2 solutions
N=5: 10 solutions
N=6: 4 solutions
N=7: 40 solutions
N=8: 92 solutionsrow − col; cells on the same ↙ anti-diagonal share row + col. Storing those two sums in sets turns each attack check into an O(1) set lookup instead of scanning the board — the difference between fast and unusable at N=12+.4 · Sudoku — constraint propagation + backtracking expert
Sudoku is backtracking on the empty cells: try 1–9 in the first empty cell, keep only digits that violate no row/column/box constraint, recurse, and undo on failure. Choosing the most-constrained cell first (fewest candidates) prunes far more — a taste of branch-and-bound heuristics.
pythondef solve_sudoku(board):
def valid(r, c, v):
for i in range(9):
if board[r][i] == v or board[i][c] == v:
return False
br, bc = 3 * (r // 3), 3 * (c // 3)
for i in range(br, br + 3):
for j in range(bc, bc + 3):
if board[i][j] == v:
return False
return True
def backtrack():
for r in range(9):
for c in range(9):
if board[r][c] == 0:
for v in range(1, 10):
if valid(r, c, v):
board[r][c] = v # CHOOSE
if backtrack(): # EXPLORE
return True
board[r][c] = 0 # UNDO
return False # no digit works -> dead end
return True # no empty cell -> solved
backtrack()
return board
puzzle = [
[5,3,0, 0,7,0, 0,0,0], [6,0,0, 1,9,5, 0,0,0], [0,9,8, 0,0,0, 0,6,0],
[8,0,0, 0,6,0, 0,0,3], [4,0,0, 8,0,3, 0,0,1], [7,0,0, 0,2,0, 0,0,6],
[0,6,0, 0,0,0, 2,8,0], [0,0,0, 4,1,9, 0,0,5], [0,0,0, 0,8,0, 0,7,9]]
solve_sudoku(puzzle)
print(puzzle[0])
print("row sums all 45:", all(sum(row) == 45 for row in puzzle))
[5, 3, 4, 6, 7, 8, 9, 1, 2]
row sums all 45: True5 · Word search — DFS with a restorable mark advanced
Find whether a word exists in a grid of letters via adjacent (up/down/left/right) cells, no cell reused. This is DFS from every start cell, marking a cell 'in use' during the path and restoring it on backtrack. The restore is the backtracking step — forget it and you falsely block reachable cells.
pythondef exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, k):
if k == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[k]:
return False
board[r][c] = "#" # MARK in-use (mutate in place)
found = (dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1) or
dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1))
board[r][c] = word[k] # RESTORE (backtrack)
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
grid = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]]
print(exist([row[:] for row in grid], "ABCCED")) # True
print(exist([row[:] for row in grid], "SEE")) # True
print(exist([row[:] for row in grid], "ABCB")) # False
True
True
False6 · Branch-and-bound & complexity expert
Plain backtracking prunes infeasible branches (a constraint is violated). Branch-and-bound also prunes sub-optimal branches on optimization problems: keep the best solution found so far, and for each partial solution compute an optimistic bound on the best it could become — if that bound cannot beat the incumbent, prune the whole subtree. It never changes the worst-case (still exponential) but slashes practical runtime.
pythondef knapsack_bnb(items, W):
"""items: list of (value, weight). Maximize value within capacity W."""
items = sorted(items, key=lambda it: it[0] / it[1], reverse=True) # densest first
n = len(items)
best = 0
def bound(i, cap, val):
"""Optimistic value: fill remaining capacity fractionally (an upper bound)."""
b, w = val, cap
for value, weight in items[i:]:
if weight <= w:
b += value; w -= weight
else:
b += value * (w / weight) # fractional fill -> can't do better
break
return b
def rec(i, cap, val):
nonlocal best
best = max(best, val)
if i == n:
return
if bound(i, cap, val) <= best: # PRUNE: even the optimistic bound loses
return
value, weight = items[i]
if weight <= cap:
rec(i + 1, cap - weight, val + value) # take
rec(i + 1, cap, val) # skip
rec(0, W, 0)
return best
items = [(60, 10), (100, 20), (120, 30)]
print("bnb knapsack, W=50:", knapsack_bnb(items, 50)) # 220
print("bnb knapsack, W=15:", knapsack_bnb(items, 15))
bnb knapsack, W=50: 220
bnb knapsack, W=15: 60| Technique | Prunes | Applies to | Worst case |
|---|---|---|---|
| backtracking | infeasible partials | constraint satisfaction | exponential |
| branch-and-bound | infeasible + provably worse | optimization | exponential |
| DP | nothing — memoizes overlap | overlapping subproblems | polynomial* |
Θ(2ⁿ), permutations Θ(n!), N-queens roughly O(n!). Pruning improves the average/practical case dramatically but does not change the worst-case class. If a problem has overlapping subproblems, DP (polynomial) beats backtracking; backtracking is for search spaces with no such overlap. (*DP is polynomial only when the state space is; 0/1 knapsack is pseudo-polynomial.)Checkpoint expert
✓ Checkpoint — you can move on when you can…
- Write the choose → explore → un-choose template from memory.
- Generate subsets, combinations and permutations and dedupe with repeated inputs.
- Explain the O(1) conflict check that makes N-queens tractable.
- Restore the grid mark after a word-search DFS branch (and say why).
- State how branch-and-bound differs from plain backtracking.
In the subsets/permutation code, why must you append path[:] instead of path?
Show answer
path is a single list mutated throughout the search — every append/pop changes it in place. Storing the reference path means every entry in result points at the same list, which is empty again once recursion unwinds. path[:] takes a snapshot copy of the current state, so each recorded solution is independent.For 0/1 knapsack, why is 'fill the remaining capacity fractionally' a valid upper bound for branch-and-bound pruning?
Show answer
🪜 Practice ladder beginner → industry
Six graded exercises, easy to real-world. Try each before opening its solution.
Context: A first 'constrained generation' backtracking problem: emit all valid combinations of n pairs of parentheses. Teaches pruning by a running invariant.
Your task: Given n, return all strings of n well-formed pairs of parentheses.
Requirements:
- Track counts of open and close parens used.
- Prune: never add ')' unless it would still be balanced (close < open).
- Only record when the string reaches length 2n.
💡 Hint: Add '(' while open < n; add ')' while close < open. Those two conditions are the whole pruning.
Show solution
pythondef generate_parentheses(n):
result = []
def backtrack(s, open_ct, close_ct):
if len(s) == 2 * n:
result.append(s); return
if open_ct < n:
backtrack(s + "(", open_ct + 1, close_ct)
if close_ct < open_ct: # prune: keep it balanceable
backtrack(s + ")", open_ct, close_ct + 1)
backtrack("", 0, 0)
return result
print(generate_parentheses(2))
print("count for n=3:", len(generate_parentheses(3))) # 5 (Catalan)
['(())', '()()']
count for n=3: 5Context: A combinations variant where numbers may be reused any number of times — the candidate-reuse pattern common in coin/target problems.
Your task: Given distinct positive candidates and a target, return all unique combinations summing to target (each candidate may be used unlimited times).
Requirements:
- Pass the current index (not index+1) to allow reuse of the same candidate.
- Prune branches whose running sum exceeds the target.
- Return combinations in a stable order.
💡 Hint: Recurse with the same start index to reuse a number; advance start to move past it.
Show solution
pythondef combination_sum(candidates, target):
candidates.sort()
result, path = [], []
def backtrack(start, remaining):
if remaining == 0:
result.append(path[:]); return
for i in range(start, len(candidates)):
if candidates[i] > remaining: # prune (sorted -> rest are bigger too)
break
path.append(candidates[i])
backtrack(i, remaining - candidates[i]) # i, not i+1 -> reuse allowed
path.pop()
backtrack(0, target)
return result
print(combination_sum([2, 3, 6, 7], 7))
print(combination_sum([2, 3, 5], 8))
[[2, 2, 3], [7]]
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]Context: Partition a string so every piece is a palindrome — a backtracking-over-cut-points problem that appears in text segmentation.
Your task: Return all ways to split a string so that each substring is a palindrome.
Requirements:
- At each position, try every prefix; recurse only if that prefix is a palindrome.
- Record a partition when you reach the end of the string.
- Verify on a short string.
💡 Hint: Loop an end index; if s[start:end] is a palindrome, choose it and recurse from end.
Show solution
pythondef partition_palindromes(s):
result, path = [], []
def is_pal(x):
return x == x[::-1]
def backtrack(start):
if start == len(s):
result.append(path[:]); return
for end in range(start + 1, len(s) + 1):
piece = s[start:end]
if is_pal(piece): # prune: only palindromic prefixes
path.append(piece)
backtrack(end)
path.pop()
backtrack(0)
return result
print(partition_palindromes("aab"))
print("count for 'aaa':", len(partition_palindromes("aaa")))
[['a', 'a', 'b'], ['aa', 'b']]
count for 'aaa': 4Context: The dedup pattern in its purest form: generate all unique subsets of a multiset. The 'skip equal siblings' trick is the crux.
Your task: Given a collection that may contain duplicates, return all possible unique subsets.
Requirements:
- Sort the input so duplicates are adjacent.
- At each tree level, skip a candidate equal to the previous one (i > start and nums[i]==nums[i-1]).
- Verify no duplicate subset appears.
💡 Hint: The condition i > start (not i > 0) allows the duplicate to be used deeper in the tree, just not as a repeated sibling.
Show solution
pythondef subsets_with_dup(nums):
nums.sort()
result, path = [], []
def backtrack(start):
result.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # skip duplicate sibling
path.append(nums[i])
backtrack(i + 1)
path.pop()
backtrack(0)
return result
subs = subsets_with_dup([1, 2, 2])
print(subs)
print("unique count:", len(subs))
[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
unique count: 6Context: The m-coloring problem (can a graph be colored with m colors so no adjacent nodes share a color?) is NP-complete and models register allocation, scheduling and map coloring. Backtracking with pruning is the standard exact solver.
Your task: Given an adjacency matrix and m colors, decide whether a proper m-coloring exists (and return one).
Requirements:
- Assign colors vertex by vertex.
- Prune: a color is legal for v only if no already-colored neighbor uses it.
- Return a valid coloring list or None.
💡 Hint: For each vertex try colors 1..m; recurse only into colors that don't clash with colored neighbors.
Show solution
pythondef graph_coloring(adj, m):
n = len(adj)
colors = [0] * n
def legal(v, c):
return all(not (adj[v][u] and colors[u] == c) for u in range(n))
def backtrack(v):
if v == n:
return True
for c in range(1, m + 1):
if legal(v, c):
colors[v] = c # CHOOSE
if backtrack(v + 1):
return True
colors[v] = 0 # UNDO
return False
return colors[:] if backtrack(0) else None
# a square cycle 0-1-2-3-0 needs 2 colors; a triangle needs 3
square = [[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]
triangle = [[0,1,1],[1,0,1],[1,1,0]]
print("square with 2:", graph_coloring(square, 2))
print("triangle with 2:", graph_coloring(triangle, 2))
print("triangle with 3:", graph_coloring(triangle, 3))
square with 2: [1, 2, 1, 2]
triangle with 2: None
triangle with 3: [1, 2, 3]Context: An exact TSP solver via branch-and-bound: prune any partial tour whose cost already exceeds the best complete tour found. This is how small routing/logistics instances are solved optimally when heuristics are not trusted.
Your task: Given a distance matrix, find the minimum-cost tour visiting every city once and returning to the start.
Requirements:
- Build tours incrementally from a fixed start city.
- Maintain the best full-tour cost found; prune any partial path whose cost already >= best.
- Return the optimal cost; verify against brute-force permutations.
💡 Hint: Depth-first extend the path; the incumbent 'best' tightens as you find complete tours, and the cost-so-far bound prunes doomed prefixes.
Show solution
pythonfrom itertools import permutations
def tsp_bnb(dist):
n = len(dist)
best = float("inf")
visited = [False] * n
visited[0] = True
def rec(city, count, cost):
nonlocal best
if cost >= best: # PRUNE: prefix already too expensive
return
if count == n:
best = min(best, cost + dist[city][0]) # close the loop
return
for nxt in range(n):
if not visited[nxt]:
visited[nxt] = True
rec(nxt, count + 1, cost + dist[city][nxt])
visited[nxt] = False
rec(0, 1, 0)
return best
def brute(dist):
n = len(dist)
return min(sum(dist[p[k]][p[k+1]] for k in range(len(p)-1))
for perm in permutations(range(1, n))
for p in [[0] + list(perm) + [0]])
dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
print("branch-and-bound:", tsp_bnb(dist), " brute:", brute(dist))
branch-and-bound: 80 brute: 80