Unit 4.1 · about 4 h
113 / 324Recursion contracts, backtracking and sound pruning
Backtracking is the baseline every smarter search must beat. If the contract is vague, pruning looks like an optimization instead of what it is: a claim that the cut branches hold no solution.
- implement
You can now
- State the contract of a recursive enumeration: the state carried, the base case, and what each call hands back to its parent.
- Implement choose, recurse, unchoose from a blank file with push-pop symmetry and snapshot-by-value, so every complete candidate is visited exactly once.
- Add a sound prune and a duplicate-skip rule, with tests that fail when the bound cuts a valid candidate or the skip misses one.
Covers
- Recursive state, base cases and return contracts
- Choice, unchoice and complete search
- Sound pruning rules and duplicate choices
Study, in this order
5 steps
- The recursion mental modelDSA Handbook - recursion, backtracking and greedy
The three parts; Worked example: tracing
factorial(4); Variants you'll meet; Common pitfallsDepth · Read for the contract shape only. Cost analysis returns in the next unit.
- The backtracking templateDSA Handbook - recursion, backtracking and greedy
What backtracking is, exactly; The three operations; The four levers; Walking LC 17 on digits 23; What it actually costs
Depth · Use LC 17 as the chassis demo. Pruning detail comes from the N-Queens item below.
- Subsets, combinations, permutationsDSA Handbook - recursion, backtracking and greedy
Subsets (LC 78); Permutations (LC 46); Combination Sum (LC 39); When duplicates show up: LC 90 and LC 47, including the warning that the two skip predicates are not interchangeable
- N-Queens: pruning and constraint propagationDSA Handbook - recursion, backtracking and greedy
The pattern; Worked example \(n = 4\); The bitmask shift, in detail; What it actually costs
- Backtracking, Chapter 2Algorithms - recursion, backtracking and greedy
2.1 N Queens (printed pp. 71-74) and 2.4 The General Pattern (printed pp. 79-80)
Focus on
- The path is identical at entry and exit: every push has a matching pop in the same scope, and every snapshot copies the
pathinstead of storing the live list. - The start-index chassis (subsets, combinations) and the used-mask chassis (permutations) take different duplicate-skip predicates. Sorting comes first in both, and the two predicates are not interchangeable.
- A prune is a claim, not a speedup: the cut branch provably holds no solution, as with a negative remaining target over positive candidates or an attacked queen square. Bitmask state passed by value needs no undo step.
- Output size sets the floor: subsets cost \(\Theta(n \cdot 2^n)\), permutations cost \(\Theta(n \cdot n!)\), and LC 46 stays small because \(n!\) explodes.
Reproduce closed-book
subsets([1, 2, 3]) returns 8 subsets; N-Queens counts are 2 for \(n = 4\) and 92 for \(n = 8\). Add a pytest file that checks every reported subset against the input set and every queen board for shared columns and diagonals.Traps
- Appending the live
pathinstead of a copy. Every snapshot aliases one list, later pushes mutate all of them, and the result finishes as copies of an emptypath. - Skipping the unchoose half on one exit path, such as an early return that pops but forgets to clear
used[i]. Keep push and pop adjacent in the same scope so no exit can split them. - An unproved prune that keeps sample tests green, such as a
breakon the first too-large candidate when the candidates were never sorted. Prove each cut, and test it against the unpruned search. Deep recursion is a separate problem: CPython stops at about 1000 frames, and raising the limit hides a depth bug instead of bounding it.
Practice
Attempt cold. Example \(n = 4\) returns 2 solutions; \(n = 1\) returns 1 solution.
After submitting, read the DSA Handbook N-Queens chapter for the bitmask form and the AlgoMaster N-Queens lesson (https://algomaster.io/learn/dsa/n-queens), and compare your prune counts with the chapter cascade.
Self-test
-
Why must the result store
path.copy()rather thanpath?pathkeeps mutating after the snapshot. Storing the reference makes every entry reflect the final emptypathinstead of the candidate at snapshot time. -
What does the plain LC 78 algorithm emit on
[1, 2, 2], and what is the fix?Eight subsets with a duplicated[2]and a duplicated[1, 2]. Sort first, then skip withigreater thanstartandnums[i]equal tonums[i-1], which keeps exactly one canonical index sequence per distinct multiset. -
Permutations run but return too few orderings. Which line is missing?
The unchoose half:used[i]set back toFalsealongsidepath.pop(). Without it the invariantsum(used)equal tolen(path)breaks and sibling branches never revisit the element. -
What makes a prune sound?
A proof that no cut branch holds a solution, for example remaining target below zero with positive candidates, or a queen square under attack. Samples alone cannot show this.
Completion criterion
Stop when
N-Queens is accepted from a cold attempt, and your own tests catch a removed copy, a removed unchoose step, and an unsound prune.
Mark passed, then open 4.2 Only mark this when you can do it without notes.Leads to
- 4.2 Divide and conquer, recurrences and partition-based selection Read the recursion-tree cost of your enumeration before calling it slow.
- 5.1 Dynamic programming states, transitions and base cases Repeated subproblems turn this chassis into memoized search later.
Comes after
- 2.7 Tries and prefix lookupWildcard search is depth-first search over trie children; that unit owns the general backtracking form.
Resources for this unit
- DSA Handbook - recursion, backtracking and greedy Study Part 7, Part 10 and the relevant foundations on recursion and probability. Write the state definition or greedy claim before opening code.
- Algorithms - recursion, backtracking and greedy Use the recursion, backtracking, divide-and-conquer and greedy chapters for recurrence derivations, proof templates and counterexamples.
Also in this section
- AlgoMaster DSA - decomposition and greedy slice Attempt N-Queens and Gas Station cold, then implement reservoir sampling and test its output distribution over fixed-seed trials. Add another judged problem only for a diagnosed weakness.
- MIT 6.042J - probability and randomized algorithms Use the probability, expectation and concentration readings to derive sampling probabilities and distinguish expected from high-probability guarantees.
- Algorithms lecture notes - randomized algorithms Use note 1 Discrete Probability, note 2 Nuts and Bolts (randomized quicksort, with QuickSelect in its exercises), note 4 Tail Inequalities and note 5 Hashing to derive expected costs, separate expected from high-probability guarantees, and analyze hashing behavior.