Greedy & Backtracking — When to Use Each

Review boundary and corrected contracts

This is a Python 3.10+ CPU-only lesson. The six main implementations and the leaf-checking N-Queens exercise are retained; tests use small exact oracles rather than timing promises. Greedy needs a proof for its precise objective. Backtracking needs complete branching, correct undo and sound pruning. Dynamic programming is not automatically polynomial.

Learning objective: triage a fresh problem into a candidate strategy, then justify the choice. A short triage is a starting hypothesis, not a promise of a proof in 30 seconds.

Why this session exists

Greedy commits to a choice, DP reuses subproblem answers, and backtracking explores alternatives while restoring state. They are not a ladder of increasing intelligence: a problem's objective, state space, constraints and required output determine which approach fits.

You will be able to

• State the greedy-choice property and optimal substructure, then give an exchange proof for activity selection.
• Write choose → recurse → unchoose and explain why the pruner cannot discard a solution.
• Distinguish an exact greedy algorithm, a bounded approximation and an unproved heuristic.
• Recognise catastrophic regex search and explain RE2's feature/performance trade-off.
• Implement activity selection, Huffman merge cost, N-Queens, subsets and permutations under explicit contracts.

Prerequisites

• S027 — Recursion: call frames, base cases and shared state.
• S033 — Dynamic Programming: state sufficiency, transitions and repeated subproblems.

Optional archived resources

These original links are retained for continuity, not used as technical evidence. Video titles, attribution, duration and playback are not reverified; a search link is not a particular lecture. Use the versioned primary sources below for contracts.

• Greedy Algorithms — Introduction
• Lecture 14 · Greedy Algorithms, Minimum Spanning Trees
• Subsets - Backtracking - Leetcode 78
• Backtracking · All Permutations, N-Queens
• Details of the Cloudflare outage on July 2, 2019
• Regular Expression Matching Can Be Simple And Fast

The archived cp-algorithms permutations URL is not relied upon for correctness or claimed to be a verified live tutorial. The self-contained code and proofs here cover its intended practice topics.

(a) Intuition · 5 min

Making change versus solving Sudoku. For the teaching denominations [1,2,5,10,20,50,100,500], taking the largest coin that fits 87 produces 50+20+10+5+2: five, not six, coins. This is a mathematical denomination set, not an assertion about currency currently in circulation. For [1,3,4] and 6, the same rule returns 4+1+1, while 3+3 is better. A successful example does not prove a coin system canonical.

In Sudoku, a locally legal digit can make a later cell impossible. Undo it and try the next candidate. Exhaustive search is complete only if all relevant choices are explored, the depth is finite, and pruning rejects only prefixes that cannot lead to the required answer.

The trap: nearest, shortest, earliest and cheapest are proposed rules, not proofs. Look for a small counterexample, then prove the remaining rule. Failure to find a counterexample is not evidence that none exists. For minimisation, an approximation guarantee would bound returned cost relative to optimum on every valid input; a heuristic with good sample results has no such bound merely because it is greedy.

Historical ideas and their limits

Huffman coding repeatedly merges low-frequency symbols; Kruskal's MST accepts light edges that join different components; Dijkstra finalises the smallest tentative distance for nonnegative edge weights. Their safe choices have different proofs. A minimum spanning tree's cut argument is not a proof of nearest-driver dispatch, and a coding theorem is not a theorem about smashing the two largest stones.

SAT connects search with complexity: propositional satisfiability is NP-complete, but this does not prove every instance needs exponential time or settle P versus NP. Practical solvers combine decisions, propagation and learned conflicts. RE2 takes a different route for a restricted regular-expression language: avoid backtracking features rather than hope pruning rescues an adversarial search. These conceptual connections replace the original unsupported “first”, “every engine” and adoption timeline claims; they are not new historical dates.

(b) When to commit and when to undo · 15 min

Activity selection shows a commitment certified by an exchange argument. N-Queens shows why a feasible prefix may still need to be undone. Follow the accepted choices and then examine which invariant justifies each action.

Greedy — activity selection worked example

Meetings are finite positive-length half-open intervals [start,end) with start < end. Touching endpoints are compatible; every meeting has unit reward, and the objective is maximum count, not duration, priority or revenue. Empty input returns an empty schedule; the function sorts a copy and does not mutate the caller's list.

Meetings: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16).

Sort by finish time and accept each start at or after the last accepted end. The scan skips overlaps; the diagram shows only accepted meetings.

Exchange proof. Let G and O be greedy and any optimal schedule, ordered by time. If they agree through k choices, greedy's next compatible interval g ends no later than O's next interval o. Replace o with g: g is compatible with the common prefix, and every later interval in O still starts at or after g's end. The replacement preserves the number of meetings and extends the agreement prefix. Repeating yields an optimum with the greedy choices. If O had an extra feasible interval after G ended, the scan would have accepted one, so their lengths agree.

The proof depends on both feasibility and objective. Earlier finish still leaves a superset of possible later intervals in a weighted problem; what fails is the claim that swapping one interval preserves value. For (0,2,w=2), (2,4,w=2), (0,4,w=9), greedy count selection earns 4 while the long interval earns 9. Weighted interval DP uses best[i] = max(best[i-1], weight[i] + best[p(i)]), where p(i) is the last compatible predecessor. Start-time sorting also fails on (0,10),(1,2),(2,3); shortest-duration sorting fails on (0,3),(3,6),(2,4).

Backtracking — the universal template

Choose extends a prefix; recurse explores completions of that prefix; unchoose restores the exact pre-call state before the next sibling. Recording uses a copy, not the mutable list shared by all calls. The “skip” edge means proceed to the next candidate. A production version that can raise exceptions during recursion needs an appropriate restoration policy, such as try/finally; this lab's pure bounded calls do not model interruption.

A feasibility prune is sound when a violated constraint cannot be repaired by extending the prefix. An optimisation prune instead needs an admissible bound: for maximisation, prune when the best possible completion cannot beat the incumbent. Pruning ties is wrong if the task asks for all optima. A timeout returns an incomplete search, not a proof of infeasibility or optimality.

N-Queens (n=4) — pruning in action

One queen per row; reject a column equal to an earlier queen's column or a diagonal with equal absolute row/column differences. Once two placed queens attack, later placements cannot undo that attack, so rejecting that prefix is sound.

The solution is [1,3,0,2]. There is also [2,0,3,1]. For n=4 the actual pruned function enters 17 recursive states, including the root and two complete boards. The unpruned tree enters 1+4+16+64+256=341 states and checks 256 complete assignments. These are fixture counts, not a universal percentage or latency guarantee. Both should find two solutions. A checker must compare row r only against earlier rows; comparing a queen with itself rejects every board.

The decision table — how to pick

A sort key is a hint, not a sufficient condition. Failed greedy does not imply DP is affordable. Backtracking and DP can also combine: memoise equivalent failed states when the stored answer remains valid for the caller's objective.

Classic winners in each camp

• Greedy: unit-weight interval scheduling; MST via Kruskal/Prim; Dijkstra with nonnegative weights; fractional knapsack; Huffman prefix-code construction. Gale–Shapley deferred acceptance is better understood via its stability invariant, not a generic maximum-weight greedy rule.
• DP: edit distance, LCS, 0/1 knapsack, matrix-chain ordering, Bellman–Ford's edge-count recurrence and finite-state Viterbi decoding. Complexity depends on the state domain.
• Backtracking: N-Queens, Sudoku, graph colouring, Hamiltonian path and constrained combinations. DFS maze reachability with a visited set can be linear in graph size; not every recursive search is exponential. Modern SAT solving adds propagation and learning rather than being plain exhaustive recursion.

A runnable greedy counterexample

These functions assume positive integer denominations with unlimited reuse and a nonnegative integer target. None from greedy means its path failed, not that no solution exists. For [3,4], target 6, greedy fails after taking 4 even though 3+3 works. The DP returns infinity when unreachable; it does not validate malformed inputs.

def greedy(coins, target):
    coins = sorted(coins, reverse=True)
    n = 0
    for c in coins:
        n += target // c
        target %= c
    return n if target == 0 else None
 
def exact(coins, target):          # exact for positive integer coins, nonnegative target
    INF = float('inf')
    dp = [0] + [INF] * target
    for t in range(1, target + 1):
        for c in coins:
            if c <= t: dp[t] = min(dp[t], dp[t-c] + 1)
    return dp[target]
 
print(greedy([1,5,10,25], 30), exact([1,5,10,25], 30))   # 2 2  - agree
print(greedy([1,3,4], 6),      exact([1,3,4], 6))        # 3 2  - greedy takes 4+1+1

Huffman merge cost is a different greedy proof

For nonnegative weights, the two smallest can be placed as deepest sibling leaves in some optimal prefix tree: exchanging lighter weights into deeper positions cannot increase weighted path length. Contract those siblings into their sum and solve the smaller tree. Expanding adds exactly that sum to the cost. Repeating gives the min-heap merge algorithm. For [4,3,2,6], merge 2+3=5, then 4+5=9, then 6+9=15: cost 29. Empty and singleton lists have merge cost zero; a file format that encodes a singleton with a bit still has its own convention. This function returns merge cost, not a code tree or a compressed byte length.

Scheduling under a deadline

An inexpensive heuristic may be appropriate for frequently changing inputs, but “milliseconds at any scale” is not a contract. Exact search gives an optimum only when complete; a solver may return an incumbent, bound, infeasible status or unknown/timeout according to its model and algorithm. Not every constraint solver reports a numeric optimality gap. Compare the online heuristic with bounded offline optima or valid bounds on recorded small workloads, and state the cost of stale decisions. Resource budgets and acceptable quality loss are engineering inputs, not proof that every online scheduler must be greedy.

(c) Hands-on · 25 min

Save as gb_lab.py and run python3 gb_lab.py. Contracts are deliberate preconditions, not runtime validators: use finite valid intervals; positive integer coins/nonnegative amounts; nonnegative integer frequencies; nonnegative integer board sizes; and distinct input values when you want value-distinct subsets/permutations.

"""gb_lab.py — greedy and backtracking classics side by side."""
from __future__ import annotations
from typing import List, Tuple
 
# ---------- GREEDY: activity selection ----------
def activity_selection(meetings: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    """Maximum-cardinality schedule of finite, positive-length half-open intervals."""
    meetings = sorted(meetings, key=lambda m: m[1])   # sort by end time
    chosen: List[Tuple[int, int]] = []
    last_end = float("-inf")
    for s, e in meetings:
        if s >= last_end:
            chosen.append((s, e))
            last_end = e
    return chosen
 
# ---------- GREEDY: coin change — optimal only with a canonical-system proof ----------
def coin_change_greedy(coins: List[int], amount: int) -> List[int] | None:
    """Positive integer coins, nonnegative amount. None means this greedy path failed."""
    coins = sorted(coins, reverse=True)
    used: List[int] = []
    for c in coins:
        while amount >= c:
            amount -= c
            used.append(c)
    return used if amount == 0 else None
 
# ---------- GREEDY: Huffman-ish — merge two lowest freq (illustrative) ----------
def huffman_cost(freqs: List[int]) -> int:
    """Optimal pairwise merge cost (Huffman construction). Real Huffman builds the tree; this is the cost."""
    import heapq
    heap = list(freqs); heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        total += a + b
        heapq.heappush(heap, a + b)
    return total
 
# ---------- BACKTRACKING: N-Queens ----------
def n_queens(n: int) -> List[List[int]]:
    """Return all N-queens solutions as lists where placed[r] = column of row r."""
    solutions: List[List[int]] = []
    placed: List[int] = []
 
    def safe(r: int, c: int) -> bool:
        for pr, pc in enumerate(placed[:r]):
            if pc == c or abs(pc - c) == abs(pr - r):
                return False
        return True
 
    def solve(r: int) -> None:
        if r == n:
            solutions.append(placed.copy())        # complete → record
            return
        for c in range(n):
            if safe(r, c):                          # prune
                placed.append(c)                    # choose
                solve(r + 1)                        # recurse
                placed.pop()                        # unchoose
 
    solve(0)
    return solutions
 
# ---------- BACKTRACKING: all subsets (power set) ----------
def all_subsets(nums: List[int]) -> List[List[int]]:
    out: List[List[int]] = []
    cur: List[int] = []
 
    def solve(i: int) -> None:
        if i == len(nums):
            out.append(cur.copy())
            return
        solve(i + 1)                                # branch: skip nums[i]
        cur.append(nums[i])                         # choose
        solve(i + 1)                                # branch: include
        cur.pop()                                   # unchoose
 
    solve(0)
    return out
 
# ---------- BACKTRACKING: all permutations ----------
def all_permutations(nums: List[int]) -> List[List[int]]:
    out: List[List[int]] = []
    used = [False] * len(nums)
    cur: List[int] = []
 
    def solve() -> None:
        if len(cur) == len(nums):
            out.append(cur.copy())
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True; cur.append(x)
            solve()
            used[i] = False; cur.pop()
 
    solve()
    return out
 
# ---------- Demo ----------
if __name__ == "__main__":
    meetings = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),
                (6,10),(8,11),(8,12),(2,14),(12,16)]
    print("Activities:", activity_selection(meetings))          # 4 meetings
 
    print("Coins for 87 (teaching denominations):", coin_change_greedy([1,2,5,10,20,50,100,500], 87))
    print("Coins for 6 (weird [1,3,4]) — greedy:", coin_change_greedy([1,3,4], 6))
    # ↑ Greedy picks 4+1+1 (3 coins); optimum is 3+3 (2 coins). GREEDY FAILS.
 
    print("Huffman cost [4,3,2,6]:", huffman_cost([4, 3, 2, 6]))
 
    print("4-queens solutions:", n_queens(4))                    # 2
    print("8-queens count:", len(n_queens(8)))                   # 92
 
    print("subsets of [1,2,3]:", all_subsets([1, 2, 3]))         # 8
    print("permutations of [1,2,3]:", all_permutations([1, 2, 3]))  # 6

Anatomy of the script

• activity_selection: sorting plus a scan is O(n log n) time and O(n) storage including the sorted copy and output. The optimum is a maximum-cardinality schedule, not the only schedule.
• coin_change_greedy: sorting d denominations costs O(d log d), then O(d+k) work for k emitted coins. The while loop is output-sensitive; zero or negative denominations violate the contract and may fail to terminate.
• huffman_cost: heapify is O(n), then n−1 two-pop/one-push merges give O(n log n) time and O(n) heap storage under a unit-cost arithmetic model. Integer bit costs grow with sums.
• n_queens: safe scans earlier rows and creates a slice, taking O(r) work/temporary storage. Search is exponential in general; a conservative bound for this implementation is O(n²·n!) candidate/check work, plus O(n·S) output for S boards. Working state is O(n) excluding output. n_queens(0) returns [[]], the empty placement; n=2 and n=3 have no solutions.
• all_subsets: index-based choices generate 2ⁿ position subsets. Materialising list copies costs O(n·2ⁿ) time/output storage, with O(n) working state. Duplicate input values create duplicate-valued outputs; removing them changes the problem.
• all_permutations: used[i] tracks positions, not distinct values. O(n·n!) time/output storage for distinct values and O(n) working state. Empty input has one permutation, []; duplicate values cause repeated value sequences. Boolean tracking versus swap-in-place is an implementation choice, not an asserted equal-speed benchmark.

What to observe and the pruning exercise

The schedule has four meetings; the 87-unit example uses five coins; weird-coin target 6 uses three instead of two; Huffman cost is 29; N-Queens counts are 2 at n=4 and 92 at n=8; three distinct elements produce eight subsets and six permutations. Remove neither the feasibility check nor the leaf validator and assume correctness survives: removing early checks requires checking completed boards instead.

Append this bounded comparison to the lab:

import time
 
def n_queens_unpruned(n: int) -> int:
    count = 0
    placed: list[int] = []
 
    def safe(r: int, c: int) -> bool:
        for pr, pc in enumerate(placed[:r]):
            if pc == c or abs(pc - c) == abs(pr - r):
                return False
        return True
 
    def solve(r: int) -> None:
        nonlocal count
        if r == n:
            if all(safe(i, placed[i]) for i in range(n)):  # check only at the leaf
                count += 1
            return
        for c in range(n):
            placed.append(c)   # NO PRUNING — always recurse
            solve(r + 1)
            placed.pop()
 
    solve(0)
    return count
 
for n in [4, 5]:
    t0 = time.time(); k1 = len(n_queens(n))
    t1 = time.time(); k2 = n_queens_unpruned(n)
    t2 = time.time()
    print(f"n={n}: pruned {k1} in {t1-t0:.3f}s  ·  unpruned {k2} in {t2-t1:.3f}s")

Exercise answer: n=4 produces 2 versus 2; n=5 produces 10 versus 10. Compare counts first, then report local elapsed time as a measurement for that machine only. Do not enlarge the unpruned exercise to n=10 (10¹⁰ leaves). At n=8 there are 8⁸ complete assignments before validation, not 8⁸ valid boards. The pruned function enters 2,057 states at n=8; the root, internal nodes and complete boards are different counting units.

(d) Production reality · 15 min

Regex: search ambiguity can consume the budget

Cloudflare's 2 July 2019 postmortem attributes global CPU exhaustion to a WAF regular expression and describes the 27-minute outage. Do not inflate this into “half the internet” or claim its specific expression had 2ⁿ states: the postmortem demonstrates superlinear retry work for its reduced expression, rather than deriving a 2ⁿ bound. Stack Overflow's 20 July 2016 postmortem describes a different unanchored whitespace regex repeatedly scanning long spaces. Superlinear retry work can be damaging even when it is not exponential.

An illustrative nested repetition such as (a+)+$ allows many ways to partition a run of a characters before a failing suffix. We do not execute a hostile regex benchmark. Prefer a bounded input/pattern policy and an engine with the required complexity contract; test near misses, not just successful matches. RE2 guarantees linear matching time in input length for a fixed pattern, budgets resources and excludes features such as backreferences and look-around. This is a feature trade-off, not drop-in compatibility with all PCRE/Python expressions. If another engine supports a timeout, test how it interrupts matching; Python's standard re API does not provide a per-call timeout parameter.

Assignment: a local match can block a better batch

Treat this as a model, not an attributed Uber deployment. Two drivers A/B and two requests X/Y have cost matrix A→X=1, A→Y=2, B→X=2, B→Y=100. Greedy assigning X to its nearest available driver A forces Y to B, total 101. The alternate assignment costs 4. A batch assignment algorithm can optimise the fixed matrix, but forecasts, travel-time estimates, acceptance and future arrivals are outside that optimum. A short window trades delay for coordination; no particular vendor cadence or speed is asserted.

Constraint search: learn a conflict, do not promise magic

For clauses (x or y) and (not x or y), trying y=false forces both x=true and x=false, a conflict. Learning the consequence y=true rules out that same failed assignment in later search. Symbolic execution supplies constraints describing a program path; a solver may produce a satisfying test input, prove the finite model unsatisfiable, or return unknown under resource/theory limits. Path explosion and modelling errors remain. Programming Z3 describes solver mechanisms; it does not establish the original ClusterFuzz incident attribution or a guarantee of exponential speedup.

Where this shows up in the rest of the plan

• Joins and indexes: query planners compare complete candidate paths and physical properties, not an independent cheapest index per predicate. PostgreSQL 16 documents near-exhaustive join search for small relation counts and a genetic heuristic beyond a threshold.
• Graph search: Dijkstra's safe finalisation uses nonnegative edge weights; A* needs an appropriate heuristic and reopening policy. A priority queue alone proves neither.
• Scheduling/load balancing: define the cost, constraints and decision window before claiming a dispatch policy optimal.
• Reinforcement learning: ε-greedy usually means choosing a current value-maximising action except for an exploration probability. Estimated action values are not a proof of global optimum.
• Regex parsing: a recogniser's language and resource guarantees are part of its contract. The old session-number labels for these later subjects were not reliable navigation.

Triage: specify the desired answer; propose a safe greedy move and prove it or reject it; assess DP state size; assess complete bounded search and sound pruning; explicitly label any heuristic or approximation. A deadline does not replace a proof.

(e) Recall + stretch · 10 min

Q: What is the greedy-choice property, in one sentence?

A: For the current subproblem there is an optimum whose first choice is the chosen greedy move; after it, optimal substructure lets us solve the remaining subproblem. Repeating this argument proves the algorithm, not merely its first move.

Q: Give one problem where greedy works and one similar-looking problem where it fails.

A: Earliest-finish selection maximises count for positive-length half-open intervals; it fails for weighted reward on (0,2,2),(2,4,2),(0,4,9), yielding 4 instead of 9. Coin denominations [1,3,4], target 6, independently refute largest-first coin optimality: 3 coins versus 2.

Q: Why do we sort by end time in activity selection instead of start time?

A: Exchanging the earliest-finishing compatible interval into an optimum preserves count and leaves the later schedule feasible. Sorting by start picks (0,10) before (1,2),(2,3), getting one meeting instead of two.

Q: Write the three lines of the backtracking template in order.

A: Choose (push candidate), recurse on the extended prefix, unchoose (pop that candidate and restore every changed constraint). Missing undo corrupts sibling state; it does not necessarily cause an infinite loop.

Q: Why is pruning the difference between ‘backtracking works’ and ‘backtracking is infeasible’?

A: Rejecting an impossible prefix saves its entire subtree. Sound pruning preserves solutions, but does not promise practicality at n≈20 or eliminate exponential worst cases. For n=4, early checks reduce entered states from 341 to 17 while retaining two boards.

Q: Give two real production systems whose bugs or performance disasters traced to backtracking.

A: Cloudflare's 2019 WAF regex and Stack Overflow's 2016 whitespace regex are documented regex-search incidents. The corrected lesson distinguishes superlinear retry work from a claim of exponential nested backtracking; their postmortems support those mechanisms, not the original unverified Node ms/Java examples.

Q: What data structure does huffman_cost use, and why is it O(n log n)?

A: A min-heap. Heapify is O(n); each of n−1 merges pops twice and pushes once, O(log n) per merge, with O(n) heap storage and unit-cost arithmetic. Empty/singleton cost is zero; [4,3,2,6] costs 29.

Q: In N-queens, describe two ways to make the safe() check faster than O(rows-so-far).

A: Maintain column, row+col and row-col sets with exact add/remove on descent/return (expected O(1) membership), or bit masks. Compute available = full & ~(cols | diag_left | diag_right), take bit = available & -available, clear it, and update shifted diagonal masks for the next row. Python integers have arbitrary width, not guaranteed 64-bit constant-cost operations. Neither optimisation promises n=20 is easy.

Q: Give the decision-triage: you see a new problem. What are the three questions you ask, in order?

A: (1) Can a particular greedy move be proved safe for this objective? (2) Is there a sufficient reusable state with affordable state/transition cost? (3) Is complete search affordable with sound pruning? The methods can combine; neither a small test set nor a timeout proves optimality.

Q: Stretch — Prove why the greedy activity-selection algorithm is optimal using the exchange argument.

A: Compare any optimum with the greedy schedule at the first differing position. Greedy's next interval ends no later, so exchange it in without breaking the common prefix or any later interval. The count is unchanged. Repeat until every greedy choice is in an optimum; an additional compatible interval would have been scanned and accepted. Thus the greedy count equals optimum. This is not a weighted-value proof.

Explain-out-loud test

1. When would you reach for greedy over DP? When a safe-choice proof and the remainder's optimal substructure establish the objective; activity selection supplies an exchange proof.
2. What is the three-line backtracking template? Choose, recurse, unchoose, with a completeness argument and a sound pruner.
3. Why is RE2 a thing? To provide bounded-resource, fixed-pattern linear-time regex matching by restricting features that require backtracking machinery.

Next practice and sources

Continue to the relational model, or drill subsets, constraint grids and greedy proofs. The learning-plan hub supplies navigation; suggested session durations are not mastery guarantees.

Corrective source notes

Primary passages inspected 10 October 2026: RE2 README, Cloudflare postmortem, Stack Overflow postmortem, Programming Z3, and PostgreSQL 16 planner. The prior DP introduction remains supplementary. Worked greedy/pruning arguments are derived here; finite CPU fixtures check exact displayed programs, not arbitrary-input correctness, engine deployment or production latency.