Three requests, three states

Using values 1,2,3: choose two; arrange two; or reuse values to total 4.

Decision: When is [2,1] a new answer after [1,2]? What information determines the next legal choice?

1 / 11

Letter Combinations of a Phone Number — predict before coding

This is a Cartesian product, not a membership search. Each digit fixes a position and supplies its allowed letters; every full tuple is an answer, so output size is an unavoidable cost.

Decision: A keypad expansion has finished the prefix "t" for digits "87". Complete the four second-letter outputs, then explain exactly which buffer state must be restored before the first letter changes to "u".

Presenter notes

Model answer: The four outputs are tp,tq,tr,ts. After each second-letter branch, the buffer returns to "t". After that first-letter branch finishes, it returns to empty before appending "u". Keeping the s would incorrectly produce three-character paths for two digits. Each recorded string must survive both restorations.

Correctness argument: At recursion depth i, the path has exactly i letters, each chosen from the corresponding digit mapping. Extending by every allowed letter preserves this invariant. At depth n the path is a legal combination and is copied into an independent string. Every possible combination has one unique sequence of choices, so it is reached once and no invalid string is emitted. Popping after each recursive call restores the prefix for the next sibling. The explicitly empty input returns an empty result rather than the mathematical Cartesian-product identity containing one empty string.

Debugging prompt: Test 7 and 9, whose mappings have four letters. Do not append a mutable path buffer by alias. Preserve the empty-input convention instead of unconditionally emitting an empty string.

2 / 11

Combinations — predict before coding

A start index breaks permutation symmetry. Once a number is chosen, later choices must be larger; [1,3] is generated once and never again as [3,1].

Decision: For n=6, k=3, prefix [2] leaves how many completions? Prefix [5] has the same length; why can it be pruned immediately? Identify the information that path length alone omits.

Presenter notes

Model answer: After [2], choose any two of {3,4,5,6}, giving six completions. After [5], only 6 remains, fewer than the two still needed. Both paths have length one, but their next-start boundaries differ. The state must include that boundary, not just the number already chosen.

Correctness argument: The current path is strictly increasing and contains only numbers below start. Choosing i>=start and recursing at i+1 preserves strictness and prohibits reuse. Every size-k subset has a unique increasing representation; following those values in order reaches it exactly once. Iterating candidates ascending gives lexicographic result order. If path length plus the count of available values is less than k, no completion can reach the required size, so pruning that suffix cannot lose a result. Recording a copied path prevents later backtracking from altering earlier combinations.

Debugging prompt: Check both row ordering and lexicographic result order, which this contract explicitly requires. Copy each completed path. An i+1 recursion differs from the i recursion used for reusable candidates.

3 / 11

Permutations — predict before coding

Positions matter here, unlike combinations. The used array tracks which input identities are already present in the current arrangement, so the next choice ranges over every unused index.

Decision: A branch has emitted [8,1,5] for input [8,1,5]. After undoing its last two choices, it starts [8,5]. Which used flags and next value are correct? Why must the emitted row remain unchanged?

Presenter notes

Model answer: Only indices 0 and 2 are used, so index 1, value 1, must be available; the next result is [8,5,1]. The earlier row represents a completed answer and cannot share writable path storage. Undoing flags controls legal future choices; copying the row separately preserves past output.

Correctness argument: Before each call, path contains distinct selected input entries and used marks exactly those entries. Marking one unused index, appending its value, and recursing adds one new position without duplication. At length n, every input entry appears exactly once, so the path is a permutation. Every permutation determines a unique order of selected indices and is therefore emitted exactly once. Unmarking and popping restore both pieces of state before the next branch. The distinct-input precondition is essential: equal input values would make different index permutations produce duplicate value rows.

Debugging prompt: Test result count n!, every row length n, exact input multiset, and absence of duplicate rows. Also mutate one returned row in a test to detect shared backing arrays without expecting input mutation.

4 / 11

Combination Sum — predict before coding

Positive reusable candidates turn the search into a nondecreasing sequence of choices. Sorting lets the first value above the remaining target stop the whole loop, not just one branch.

Decision: Candidates are [3,5] and target is 11. A branch begins with 5 and has remaining total 6. Why must that branch not append 3, even though [5,3,3] sums correctly? Where is the answer generated?

Presenter notes

Model answer: The branch starting at candidate 5 may reuse 5 but may not move back to candidate 3. Otherwise the same multiset would be emitted in several orders. The increasing-index traversal generates its unique sorted representation [3,3,5] from the branch beginning with 3; it needs to recurse at the same index to allow the second 3.

Correctness argument: The path sum plus remaining equals the original target, and candidate indices along the path never decrease. Selecting index i and recursing again at i permits reuse while excluding reorderings of the same multiset. Since candidates are distinct and positive, every valid multiset has one sorted representation, and each recursive step strictly decreases remaining. The branch reaching remaining zero is exactly a valid sum. Once a sorted candidate exceeds remaining, all later candidates do too, so none can complete the path. This proves termination, completeness, and duplicate avoidance under the positive-distinct preconditions.

Debugging prompt: Zero candidates destroy the decreasing-remaining argument; negative candidates destroy sorted upper-bound pruning. They are outside the contract. The reference sorts candidates in place, so copy them when order must be retained.

5 / 11

Generate Parentheses — predict before coding

Validity can be enforced on prefixes. An opening is allowed until n are used; a closing is allowed only when it matches an already unmatched opening.

Decision: For n=3 pairs, a proposed closing rule is “append ) when closeUsed<=openUsed.” Construct the shortest nonempty balanced prefix from which this rule makes an invalid next prefix. Which inequality fixes it?

Presenter notes

Model answer: Prefix () has openUsed=closeUsed=1. Appending another close gives ()), whose third position has more closes than opens. A balanced unfinished prefix may open another pair, but has no unmatched opening to close. The guard before appending must be closeUsed<openUsed.

Correctness argument: Every generated prefix satisfies 0<=close<=open<=n. The opening transition preserves the upper bound, and the closing transition preserves nonnegative balance. At length 2n these inequalities force open=close=n, so every emitted string is balanced. Conversely, every well-formed target string satisfies the same prefix inequalities, so its next character is always one of the permitted branches; following its characters reaches it. Distinct branch sequences produce distinct strings. Restoring the buffer after each branch preserves the parent prefix, and copying on output prevents later writes from changing an answer.

Debugging prompt: Test every prefix balance, total length 2n, and uniqueness, not merely equal total counts. The string )( has equal totals but fails prefix validity.

6 / 11

N-Queens II — predict before coding

Placing exactly one queen per row removes one dimension of choice. Columns and the two diagonal identifiers summarize every conflict with earlier rows.

Decision: On a 4-by-4 board, earlier queens are (0,0) and (1,2). Show why row 2 has no legal column. Does that failure mean row 0 must immediately move, or is there still another branch to explore first?

Presenter notes

Model answer: Columns 0 and 2 are occupied. Columns 1 and 3 both share a diagonal with (1,2), so no column is legal. Undo the queen at (1,2), restoring its column and both diagonals, and try other row-1 columns before abandoning (0,0). A dead row rejects the current prefix, not every prefix with the same first queen.

Correctness argument: Before placing row r, rows 0..r-1 each contain one queen and the occupied-column and diagonal arrays describe exactly those queens. A candidate column is legal precisely when its column, r-c offset, and r+c sum are unoccupied. Marking those three lines and recursing maintains non-attacking placement. Unmarking restores the earlier-row state for another candidate. Reaching row n gives one complete placement; every valid placement has one unique row-by-row column sequence, so the traversal counts it once and omits none. Offset r-c by n to use nonnegative array indices.

Debugging prompt: Undo all three markers, not only the column. Test n=1,2,3,4: their counts are 1,0,0,2. Do not divide by rotations/reflections; the contract counts distinct placements separately.

7 / 11

Word Search — predict before coding

The same board cell may participate in different candidate paths, but not twice in one path. Visited state therefore belongs to one recursive branch and must be restored even when that branch succeeds.

Decision: On the one-row board ABA, can the word ABA be found? A learner stores visited letter values instead of visited cell positions. What valid step would that reject, and does the board support ABAA?

Presenter notes

Model answer: ABA is valid using three distinct positions 0,1,2. A set of letter values would reject the final A merely because the first A was used, confusing value equality with cell identity. ABAA is impossible because four word positions require four distinct cells and only three exist. A correct successful or failing query leaves the board unchanged.

Correctness argument: At a matching cell for word position i, the cells marked by earlier calls are exactly the already-used prefix path. Rejecting mismatched or marked cells ensures the next chosen cell extends that path by one unused adjacent location. Reaching the final matching character proves a complete legal path. Trying all four neighbors covers every possible extension, and trying every start cell covers every possible first location. Restoring the board on both successful and unsuccessful returns prevents a completed branch from removing possibilities elsewhere and guarantees the caller sees the original board.

Debugging prompt: Compare the entire board before and after both successful and failing queries. The temporary # marker must be outside the letter alphabet. Empty words are outside the stated positive-length contract.

8 / 11

Word Search — is the cache key complete?

Board AAA / ABA; word BAAAA; start B=(1,1).

Both prefixes reach A=(0,0) at word index 2:

(1,1)->(0,1)->(0,0)
(1,1)->(1,0)->(0,0)

Decision: Why may a cached failure for the first prefix not reject the second?

9 / 11

Change the spacing rule

Choose three nonconsecutive days from days 1..6.

Derive the next-start rule. List all answers. Give a prune that uses the changed spacing.

10 / 11

Reconstruct and transfer

Reconstruct the branch state, decreasing measure, prune proof, restoration, and output-copy point.

Include output length in the complexity.

11 / 11