Greedy Algorithms & Backtracking

The greedy idea and how to prove it

A greedy algorithm builds a solution one piece at a time, always taking the locally best piece according to some rule, and never revisiting a decision. Dijkstra (always settle the closest vertex) and Prim and Kruskal (always add the cheapest safe edge) from M31 are greedy.

Greedy works when the problem has two properties:

• Greedy choice property: some optimal solution begins with the greedy choice.
• Optimal substructure: after making the greedy choice, what remains is a smaller instance of the same problem, and an optimal solution to it combines with the greedy choice into an optimal whole.

The standard proof technique is the exchange argument: take any optimal solution O that does not start with the greedy choice g. Show you can swap g into O in place of some element without making it worse. Then there is an optimal solution that starts with g, and induction finishes the proof.

Remember: greedy = one pass, no regrets. It is correct only with a proof; DP (M32) is the safe fallback when choices interact.

Interval scheduling and interval merging

Activity selection: given meetings as (start, end) intervals and one room, schedule as many as possible. Candidate greedy rules: shortest first? earliest start first? fewest conflicts first? All three fail on some input. The rule that works is earliest end time first.

Exchange argument. Let g be the meeting that ends first. Take any optimal schedule O, and let o be its first meeting. Since g ends no later than o, replacing o with g conflicts with nothing else in O, and the count is unchanged. So an optimal schedule starts with g; remove everything overlapping g and repeat. Sorting dominates: O(n log n).

Merging intervals: sort by start; walk through, extending the current block while the next interval starts before the block ends. Also O(n log n), and the basis of calendar "busy" views.

A third classic: the minimum number of rooms for all meetings equals the maximum number of meetings in progress at once. Sort starts, keep a min-heap of end times (M25), and pop rooms that are free. You will build this in the mini-project.

When greedy fails: coin change

"Take the largest coin that fits" makes change optimally for US coins (1, 5, 10, 25). Many people assume it always works. It does not.

At 6, greedy takes 4 + 1 + 1 (three coins) while 3 + 3 uses two. The exchange argument breaks: you cannot swap the 4 into the optimal solution {3, 3} without making it worse. Coin systems where greedy is always optimal are called canonical; deciding canonicity is itself a nontrivial algorithm. When in doubt, use DP.

Huffman coding

Store text with fewer bits by giving frequent characters short codes and rare ones long codes. For decoding to be unambiguous, no code may be a prefix of another (a prefix code), which is the same as saying the codes are leaves of a binary tree: 0 = left, 1 = right.

Huffman's greedy rule: repeatedly merge the two least frequent trees into one whose weight is their sum. A min-heap makes each step O(log k), so the whole build is O(k log k) for k distinct symbols.

Why it is optimal (sketch). In some optimal tree the two rarest symbols are sibling leaves at the deepest level: if a rarer symbol were shallower than a more frequent one, swapping them would not increase the total cost (exchange argument). Merging those two into one pseudo-symbol leaves a smaller instance of the same problem, so induction applies.

Fractional knapsack: greedy wins where 0/1 needs DP

If you may take fractions of items (gold dust rather than gold bars), sort by value per unit weight and take as much of the densest item as fits, then the next. Exchange argument: any solution that holds some weight of a less dense item while a denser one is not fully taken can be improved by swapping that weight. O(n log n).

Remember: a tiny change in the rules (fractions allowed or not) can switch a problem between greedy and DP. Always re-check the exchange argument.

Backtracking: depth-first search over choices

Many problems ask you to construct something: a subset, an ordering, a placement. Backtracking explores the tree of partial solutions depth-first. At each node it chooses an option, explores recursively, then un-chooses it so the next option starts from a clean state. If a partial solution already violates a constraint, the whole subtree is skipped: that is pruning.

def backtrack(partial):
    if is_complete(partial):
        record(partial)
        return
    for option in options(partial):
        if is_consistent(partial, option):   # prune
            partial.append(option)          # choose
            backtrack(partial)              # explore
            partial.pop()                   # un-choose

N-queens and sudoku

N-queens: place n queens on an n × n board so none attack each other. Place one queen per row; for each row try each column, skipping columns and diagonals already attacked. Tracking attacked columns and diagonals in sets makes each check O(1): cells on one "\" diagonal share row - col, cells on one "/" diagonal share row + col.

Sudoku: find an empty cell, try each digit that does not clash with its row, column, or box, recurse, and undo on failure. Plain backtracking already solves most newspaper puzzles in milliseconds; the next section makes it robust.

Pruning, constraint propagation, and branch and bound

Backtracking is exponential in the worst case, so its speed is entirely about how much of the tree you avoid.

• Feasibility pruning: stop as soon as a partial solution breaks a constraint (the N-queens attack check).
• Variable ordering, MRV: branch on the variable with the fewest remaining options. A sudoku cell with one candidate costs no branching at all; a cell with nine multiplies the tree by nine.
• Constraint propagation: after each choice, deduce forced consequences. If an empty sudoku cell has exactly one candidate (a naked single), fill it; if any cell has zero, fail immediately. Propagation often solves easy puzzles with no guessing.
• Symmetry breaking: in N-queens, try only the left half of the first row and double the count (careful with the middle column for odd n).

Branch and bound

For optimization searches (find the best, not just any), keep the best complete solution found so far. At each node compute an optimistic bound on any solution in its subtree; if the bound cannot beat the incumbent, prune. For 0/1 knapsack the fractional-knapsack value of the remaining items is a valid upper bound (you can never do better than the relaxation). Good bounds plus good ordering (try the most promising branch first so the incumbent improves early) let branch and bound solve instances far beyond brute force. It is the core of integer-programming solvers.

Practice

def min_arrows(balloons: list[tuple[int, int]]) -> int:
    arrows = 0
    last = None
    for start, end in sorted(balloons, key=lambda b: b[1]):
        if last is None or start > last:
            arrows += 1
            last = end
    return arrows

def first_greedy_failure(coins: list[int], limit: int) -> int | None:
    best = [0] * (limit + 1)
    for a in range(1, limit + 1):
        best[a] = 1 + min(best[a - c] for c in coins if c <= a)
    desc = sorted(coins, reverse=True)
    for amount in range(1, limit + 1):
        left, used = amount, 0
        for c in desc:
            used += left // c
            left %= c
        if used > best[amount]:
            return amount
    return None

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    nums = sorted(candidates)
    out: list[list[int]] = []
    cur: list[int] = []

    def go(start: int, remaining: int) -> None:
        if remaining == 0:
            out.append(cur.copy())
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break                      # sorted, so every later candidate overshoots too
            cur.append(nums[i])
            go(i, remaining - nums[i])     # i, not i + 1: reuse allowed
            cur.pop()

    go(0, target)
    return out

def queens(n: int) -> list[tuple[int, ...]]:
    out: list[tuple[int, ...]] = []
    placed: list[int] = []
    cols: set[int] = set()
    diag: set[int] = set()
    anti: set[int] = set()

    def go(row: int) -> None:
        if row == n:
            out.append(tuple(placed))
            return
        for col in range(n):
            if col in cols or row - col in diag or row + col in anti:
                continue
            placed.append(col); cols.add(col); diag.add(row - col); anti.add(row + col)
            go(row + 1)
            placed.pop(); cols.remove(col); diag.remove(row - col); anti.remove(row + col)

    go(0)
    return out

PEERS = []
for i in range(81):
    r, c = divmod(i, 9)
    br, bc = 3 * (r // 3), 3 * (c // 3)
    group = {9 * r + j for j in range(9)} | {9 * k + c for k in range(9)}
    group |= {9 * rr + cc for rr in range(br, br + 3) for cc in range(bc, bc + 3)}
    PEERS.append(group - {i})

def solve_sudoku(puzzle: str) -> str | None:
    cells = [0 if ch == "." else int(ch) for ch in puzzle]

    def candidates(i):
        return set(range(1, 10)) - {cells[p] for p in PEERS[i]}

    def go() -> bool:
        best, best_opts = None, None
        for i in range(81):
            if cells[i] == 0:
                opts = candidates(i)
                if best_opts is None or len(opts) < len(best_opts):
                    best, best_opts = i, opts
                    if not opts:
                        return False
        if best is None:
            return True
        for d in best_opts:
            cells[best] = d
            if go():
                return True
        cells[best] = 0
        return False

    for i, v in enumerate(cells):
        if v and v in {cells[p] for p in PEERS[i]}:
            return None
    return "".join(map(str, cells)) if go() else None

Mini-project

pixi init scheduler && cd scheduler
pixi add python pytest
pixi run python scheduler.py meetings.csv
pixi run pytest -q

Quiz

Recap

• Greedy commits to the locally best choice. It needs the greedy choice property plus optimal substructure, proved with an exchange argument.
• Earliest-end-first schedules the most intervals; merging sorts by start; Huffman merges the two rarest trees; fractional knapsack takes the densest first.
• Greedy coin change fails for non-canonical systems such as [1, 3, 4]; use DP.
• Backtracking is DFS over partial solutions: choose, explore, un-choose, and prune inconsistent branches.
• Subsets (2ⁿ), permutations (n!), and combinations (C(n, k)) are the three basic search trees.
• MRV, constraint propagation, symmetry breaking, and branch-and-bound bounds turn hopeless searches into fast ones.

Going further

• heapq: heap queue algorithm
• itertools combinatoric iterators
• Peter Norvig, "Solving Every Sudoku Puzzle"
• Next: M34 Strings, Bits & Number Theory; apply backtracking and propagation in the Puzzle Solver Suite.