Backtracking & branch-and-bound

1 · The backtracking template advanced

Picture yourself lost in a hedge maze. You reach a fork, pick the left path, walk until you hit a dead end — and what do you do? You don't teleport home and start over. You walk back to the last fork, remember that "left" was a bust, and try "right" instead. If that branches into more forks, you repeat: go deep, hit a wall, retreat one step, try the next door. That instinct — explore a choice fully, and if it fails, quietly undo it and try the next — is backtracking. The whole family of algorithms in this chapter is just that maze-walking discipline written down carefully.

Here's why it deserves its own chapter rather than being "just recursion." A huge class of problems have the same shape: build a solution one decision at a time, where each decision opens up more decisions, and most partial choices lead nowhere. Placing queens on a chessboard, filling a Sudoku grid, choosing which items to pack — they're all "make a sequence of choices, and when one turns out impossible, back up." If you tried to write bespoke logic for each, you'd drown. Backtracking gives you one skeleton that solves them all, and once you internalise it your job on any new problem shrinks to answering three small questions: what's a choice here, when am I done, and when is a branch hopeless?

The mental model is a decision tree. The root is "nothing decided yet." Every edge is one choice you could make; every path from the root downward is a partial solution being built. Backtracking is a depth-first walk of that tree — dive down one path as far as it goes, and when you can't continue, climb back up to the nearest unexplored branch. The tree is almost never stored in memory; it exists only implicitly, in the shape of your recursive calls. That's the beautiful part: a few lines of recursion traces out an enormous tree without ever building it.

Concretely, at each node you do three things in strict order. You choose an option (add it to your running path). You recurse to explore every consequence of that choice — the whole subtree beneath it. Then, crucially, you un-choose: you undo the exact change you just made, restoring the state to what it was before, so the next option starts from a clean slate. A base case notices when the path is a complete solution and records it; a pruning check notices when a partial path can't possibly succeed and abandons that entire subtree without exploring it.

The mistake that bites every beginner is forgetting to un-choose. It's seductive to write "choose, recurse" and move on — the code even runs — but without the matching undo, your leftover choices leak into sibling branches. Suddenly you're placing a queen on a square that's still marked "occupied" from a path you supposedly abandoned, and your answers are silently wrong. The rule that saves you: choose and un-choose must be exact mirror images. Whatever you did on the way down (append an element, mark a cell, add to a set), undo precisely that on the way back up — same element, same cell, same set. If you can't point at the line that reverses each choice, the code is broken even when it looks fine.

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^3

2 · Permutations & combinations intermediate

Think about the difference between a lock combination and a lottery draw. A "combination lock" is misnamed — 42-17-9 opens it and 9-17-42 does not, so order matters; that's really a permutation. A lottery draw is the opposite: pick 6 numbers and it makes no difference whether you wrote them down as {3, 14, 22} or {22, 3, 14} — the same six balls win either way, so order is irrelevant. That single question — does the order of my choices matter? — is what separates the two most common backtracking outputs, and getting it wrong is the difference between generating six results and generating twenty-four.

Both come straight from the §1 template; only the branching rule changes. For combinations you want each group counted once, so you must never look backward: once you've considered element i, later picks may only come from i+1 onward. That's the whole trick of passing a start index — it forbids "going back," which is exactly what would produce {1,2} and {2,1} as separate answers. For permutations order does matter, so you're allowed to reach any element you haven't already placed; you just need a way to remember which ones are spoken for, which is what the used[] flags do. Same choose/recurse/un-choose bones — a different question asked at each node.

It helps to feel how fast these grow, because it explains why "just enumerate them all" stops working almost immediately. Combinations count C(n,k) and permutations count n!. That factorial is vicious: 10 items have 3.6 million orderings, 13 items have over 6 billion, and 20 items have more permutations than there are grains of sand on Earth. So these algorithms are inherently exponential-to-factorial — no cleverness makes generating all of them cheap, because the output itself is that large. The lesson isn't "optimise the generator"; it's "if n is more than a dozen or so, you almost certainly want to prune, sample, or reformulate rather than list everything."

The common mistake here is the double-count. Beginners write a permutation-style loop (reach any unused element) when they meant combinations, and get every group in every order — then "fix" it by dumping results into a set and hoping duplicates vanish. That works but wastes exponential effort generating garbage you throw away. The disciplined fix is structural: use the start index to make duplicates impossible to generate in the first place, rather than filtering them afterward. Prevention beats cleanup, especially when the thing you're cleaning up grows factorially.

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

3 · N-queens — pruning by constraint advanced

Imagine trying to seat eight feuding relatives at a dinner where any two who can "see" each other along a row, column, or diagonal will start a fight. The brute-force approach — try every possible arrangement and check each — is hopeless: on an 8×8 board there are billions of ways to drop eight queens, and the vast majority are illegal the instant the second queen lands. N-queens is the classic teaching problem for the single most important idea in this chapter after the template itself: pruning. Instead of building doomed arrangements to completion and rejecting them at the end, you reject them the moment they become impossible — and that turns an intractable search into an instant one.

The key reframing is to bake the constraint into how you build. Two queens can never share a row, so don't even consider arrangements where they do: place exactly one queen per row, working top to bottom. That one decision collapses the search from "choose 8 squares out of 64" to "choose a column for row 0, then row 1, then row 2…" — a much smaller tree. Now at each row you only ask a narrow question: which columns are safe given the queens already placed above? A column is safe if no earlier queen sits in that same column or on either diagonal running through it.

Here is where pruning earns its keep, and it's worth seeing why it's so powerful. Suppose your first three queens are placed and they leave no safe square in row 3. A brute-force enumerator wouldn't notice — it would keep trying to fill rows 4 through 7 anyway, generating and discarding thousands of arrangements built on a foundation that was already broken. Backtracking sees the dead end at row 3 and immediately climbs back to reconsider row 2, never wasting a single step on the impossible subtree. One violated constraint prunes an entire exponential branch. That's the difference between exploring N^N placements and the tiny fraction that could actually work.

The mistake to guard against is checking constraints too late or too slowly. If you place all N queens first and only then ask "is this legal?", you've thrown away every ounce of pruning — you're back to brute force with extra steps. Prune as you place, at every row. And watch the second trap: writing the safety check as a scan over the whole board (an O(N) or worse test) inside a search that runs millions of times. The lab below shows the professional move — encoding columns and both diagonal families as sets so each "is this square attacked?" question is answered by an O(1) lookup. Prune early and prune cheap.

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 solutions

4 · Sudoku — constraint propagation + backtracking expert

Watch how you actually solve a Sudoku by hand and you'll find you're already backtracking. You scan for an empty cell, pencil in a digit that looks legal, and carry on — until somewhere down the line you reach a cell where nothing fits. At that point you erase your way back, change an earlier guess, and continue. Human solvers hate that "erase back" step because it feels like wasted work, but it's precisely the choose → explore → undo cycle from §1, applied to a 9×9 grid. Sudoku is the perfect bridge from "toy puzzle" to "real constraint-satisfaction problem," because the same machinery scales up to scheduling, seating, and resource allocation.

The structure is: the empty cells are your sequence of decisions, and the digits 1–9 are the options at each one. You choose a digit for an empty cell, recurse to solve the rest of the grid given that choice, and if the recursion reports failure you undo (clear the cell back to empty) and try the next digit. The base case is subtle and elegant: if you scan the whole grid and find no empty cell, the puzzle is solved — there's nothing left to decide. Failure is the mirror image: if some empty cell has no legal digit, this branch is a dead end and you return up the tree.

Pruning here comes from Sudoku's three rules — no repeat in a row, a column, or a 3×3 box. Every one of those is a chance to reject a digit before you commit to it, which is what keeps the search from exploding. This is constraint propagation in its simplest form: each placement immediately shrinks the legal options for its neighbours. The truly powerful move, hinted at in the code, is choosing which empty cell to fill next. Instead of always taking the top-left blank, pick the cell with the fewest legal candidates — if some cell can only hold a 7, decide it now. Filling the most-constrained cell first means you either make forced moves (no branching at all) or discover contradictions fast, and it's a direct taste of the branch-and-bound heuristics in §6.

The classic bug is, once again, an incomplete undo — but Sudoku adds its own twist. Because the grid is a shared mutable structure passed through every recursive call, a digit you fail to clear on the way back up doesn't just corrupt one branch; it poisons the validity checks for every sibling attempt, and you'll get "unsolvable" reports for puzzles that are perfectly solvable. Set the cell, recurse, and if that fails set it back to 0 before trying the next digit — no exceptions. The second trap is trusting a solution you never verified; the lab confirms the result by checking that every row sums to 45, the fingerprint of a valid grid.

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: True

5 · Word search — DFS with a restorable mark advanced

Think of the word-find puzzles in a newspaper — a grid of letters, and you drag your finger from cell to neighbouring cell trying to spell a target word, never crossing your own trail. When a path fizzles out, you lift your finger back to where it went wrong and try a different direction. That physical "trace a path, and if it dead-ends, retrace and branch off" is backtracking on a grid, and the finger you can't cross twice is the one detail that turns a simple search into a genuine backtracking problem.

Mechanically this is depth-first search launched from every starting cell (the word could begin anywhere), where each step tries the four neighbours — up, down, left, right — that match the next letter. The choice at each node is "which adjacent cell do I step to?"; the base case is "I've matched every letter, success"; the dead ends are "off the board," "letter doesn't match," or "already on my path." Because the word snakes through the grid one letter at a time, it's the template again — just with the decision tree laid over a 2-D board instead of a list.

The heart of this section is the "no cell reused" rule, and it forces a technique worth naming: the restorable mark. As you step onto a cell you mark it in use (here by overwriting it with a placeholder like #), so the recursion can't step back onto it and count the same letter twice. But — and this is the entire point — when that branch returns, you must restore the cell to its original letter. Marking is your "choose"; restoring is your "un-choose." They are the mirror-image pair from §1, expressed as a single mutable cell rather than a list you append to and pop from.

Forgetting the restore is the signature bug of this problem, and it's insidious because the code still runs and often gives the right answer on small inputs. If you mark a cell in use and never clear it, that cell stays blocked for every other path that would legitimately want to pass through it later — you've falsely walled off reachable squares, and words that genuinely exist get reported as missing. The failure is silent and data-dependent: it only shows up when two possible paths would have shared a cell. The fix is the discipline you now know by heart: mark on the way down, restore on the way back up, every single time. Note too that the lab passes a copy of the grid to each call so the mutation never leaks between test cases — a real-world habit worth copying.

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
False

6 · Branch-and-bound & complexity expert

Suppose you're shopping for the cheapest flight itinerary and you've already found one that costs $600. Now you start pricing out a new route, and after just the first two legs the running total is already $650. Do you bother pricing the remaining legs? Of course not — it's already more expensive than the best you've found, and adding more legs can only make it worse. You abandon it on the spot. That instinct — "this partial answer already can't win, so don't finish it" — is the leap from plain backtracking to branch-and-bound, and it's what lets you find a provably optimal answer without checking every possibility.

The distinction is worth stating precisely because it's a favourite interview question. Plain backtracking prunes branches that are infeasible — they break a hard rule, like a queen attacking another or a Sudoku digit repeating. Branch-and-bound handles a different flavour of problem: optimization, where every complete answer is legal but you want the best (cheapest, most valuable, shortest) one. So it prunes a second kind of branch on top of the infeasible ones — the branches that are still legal but provably worse than a solution you've already got in hand.

Two pieces make it work. First, the incumbent: the best complete solution found so far — your $600 flight. It starts pessimistic (infinity for a minimization, zero for a maximization) and tightens every time you complete a better solution. Second, and this is the clever part, the bound: for any partial solution you compute an optimistic estimate of the best it could possibly become if everything went perfectly from here. For a minimization that's a lower bound; for the knapsack in the lab it's an upper bound found by pretending you can pack items fractionally. If even that best-case estimate can't beat the incumbent, the entire subtree is hopeless and you prune it. The bound must be genuinely optimistic — never worse than reality — or you might prune the true optimum by mistake.

Now the honest part, because this is where hype meets math. Branch-and-bound does not change the worst-case complexity — it's still exponential, because a pathological instance can force you to explore nearly the whole tree. What it changes is the practical runtime, often by orders of magnitude, by skipping vast doomed regions. Keep this straight from a genuinely different technique: dynamic programming (D10–D11) attacks problems with overlapping subproblems by memoizing repeated work, and can drop you to polynomial time. Backtracking and branch-and-bound are for search spaces with no such overlap, where you must genuinely explore — you just explore as little of it as you can get away with. The comparison table and the closing warning make this trade-off explicit: prune all you like, but don't fool yourself that pruning turns exponential into polynomial.

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

Checkpoint expert

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: 5

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]]

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': 4

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: 6

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]

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