Backtracking

Reader guide and study workflow · Complete course map

Suppose a program must produce all legal arrangements, not merely decide whether one exists. Before writing recursion, decide what counts as the same answer. The following three requests look similar but have different search trees:

Request using values 1,2,3	Is [2,1] a new answer after [1,2]?	May a value repeat?
Choose two values	No	No
Arrange two distinct values	Yes	No
Reach total 4 using reusable values	No; order is irrelevant	Yes

Enumerating every possible sequence and removing duplicates afterward works on tiny inputs. It also does work that the output contract never asked for. The useful improvement is to prevent equivalent or invalid branches before they grow.

Derive the branch state from the answer

For choosing two values, represent every answer in increasing order. After choosing 2, only 3 is available. A call needs start, the first eligible value, plus the path already chosen; choosing i advances start to i+1. That one boundary removes the [2,1] duplicate without a result set.

For arrangements, increasing order would throw away valid answers. Keep a used flag per input index instead. After choosing 2, both 1 and 3 are still legal. The flags must describe exactly the current path, not everything ever visited during the whole search.

For reusable sums, choosing 2 may need another 2. Recurse with the same candidate index i, not i+1. Track remaining total, maintaining sum(path)+remaining=target. Positive candidates guarantee remaining strictly decreases; zero would destroy this termination argument and negative values would invalidate the “too large” prune.

These are three state designs derived from identity and reuse rules. They are not interchangeable versions of a generic recursion template.

Prove a prune before trusting it

With n=5, k=3 and prefix [2,4], only 5 remains, and exactly one more value is required: finish [2,4,5]. With prefix [4], two values are required but only 5 remains: no suffix can succeed. The same count comparison works before descending any branch.

For parentheses, a prefix with more closes than opens is already invalid; later openings cannot repair an earlier unmatched close. For N-Queens, a column or diagonal already occupied by an earlier queen cannot become legal by placing more queens. Both prunes discard an impossible completion, not merely an unattractive one.

A complete branch contract has four parts:

entry: shared state describes exactly the current legal prefix
choose: record one permitted extension
explore: solve the strictly smaller remaining decision
exit: restore the shared state to its entry value

Word Search makes the exit obligation visible: even a successful branch must undo temporary board marks. Enumeration adds a different ownership obligation: a returned answer must be a copy, so future branches cannot overwrite it. Recursion may share the workbench; results must survive after the workbench changes.

Transfer: change one rule, rebuild the state

Choose three days from days 1 through 6, with no two chosen days consecutive. Order of selection is irrelevant. Derive the next-start rule, enumerate the answers, and decide whether a used-index array is necessary.

Model answer: enforce the new gap at the boundary

After choosing i, recurse with start=i+2. The increasing boundary prevents reorderings and reuse; the extra gap prevents consecutive days. The four answers are [1,3,5], [1,3,6], [1,4,6], and [2,4,6]. A used array adds no information because everything below start is already ineligible.

If t further choices are needed and the next eligible day is s, the earliest possible finish is s+2*(t-1). A value greater than 6 proves this branch impossible. For example, after prefix [2,5], one choice is still needed but start=7, so prune. This bound follows from the changed spacing rule; blindly reusing the ordinary count of remaining days would give a weaker prune.

Choose the next practice by the decision it isolates

• Keypad combinations isolate one choice per fixed position; there is nothing to deduplicate.
• Combinations, Permutations, and Combination Sum isolate answer identity and reuse.
• Generate Parentheses and N-Queens isolate constraints summarized by a small state.
• Word Search tests whether a branch can borrow mutable input and restore it, and whether a proposed cache key actually contains all future-relevant information.

Use backtracking when legal possibilities must be explored and the constraints make the remaining search practical. Before coding, write the branch state, the strictly decreasing measure, one justified prune, and exactly what must be restored. If two histories with the same proposed state have different legal futures, that state is incomplete.

Prerequisites and readiness

Know recursion with decreasing measures, slice backing arrays, and choose/explore/undo state restoration. Be able to distinguish combinations, permutations, and reusable multisets before selecting a recursion signature.

Reasoning workshop: define a branch and its restoration

Three search trees that should not share one template

Complete these next-call decisions without opening the first section again:

Partial request	Next decision to derive
Choose three values from 1..6; current prefix [2,4]	Which next values are legal?
Arrange [2,4,6]; current prefix [4]	Which indices must remain available?
Reusable candidates [3,4], remaining target 7, after already choosing 3	May another 3 be chosen?

Model answer: the signature expresses the requested object

The combination can next choose 5 or 6, because every answer has a unique increasing representation. The permutation must still allow indices 0 and 2, corresponding to 2 and 6; only index 1 is used. The reusable sum may choose another 3 and later 4, giving [3,3,4] for original target 10. Advancing past the current candidate would lose that valid multiset.

The first state needs an increasing start boundary, the second needs a used-index set, and the third needs a nondecreasing start plus remaining target. Path length alone cannot describe all three futures.

Write a conservation equation for the actual branch: sum(path)+remaining=target for reusable sums; len(path)=digit index for keypad expansion; all chosen values below start for combinations; used marks exactly path entries for permutations. After a sibling returns, every borrowed state component must match its earlier value.

Prefix validity gives safe pruning

For n=3 parentheses, prefix (() has two opens and one close. Either next character is legal. Prefix ()) is impossible because a closing appears before its matching opening; no suffix can repair that earlier invalid prefix. Generate only prefixes satisfying 0<=close<=open<=n. Equal final totals alone are insufficient: )( has one of each but is not well formed.

For combinations, if the path still needs three values but only two remain in 1..n, abandon the branch. For positive Combination Sum candidates sorted ascending, a value larger than remaining allows the entire rest of that loop to stop. Neither argument survives arbitrary negative candidates. A prune is justified by an impossibility proof, not by looking unlikely to succeed.

State can be shared while answers must be independent

A mutable path buffer saves allocation during exploration, but appending the slice itself to results can make all answers share the same storage. Copy at the point a complete answer is recorded. Undo by restoring the previous slice length and any flags. For N-Queens, undo column and both diagonal markers; restoring only one of them silently removes legal sibling branches.

With queens at (0,1) and (2,3), row-column is -1 for both, so they attack along one diagonal. The two families are row-column and row+column, with an offset for negative array indices. Exactly one queen per recursion row already enforces the row constraint.

Successful search still owes restoration

Word Search is an existence query, so it can stop early after finding a path. But temporary board marks still belong to the recursive calls on that successful path. Restore before each early return. On [A,B], ABA is impossible because the same A cell cannot be reused; on a larger board another A could complete it. A global visited set would incorrectly forbid reuse across different candidate paths.

A failed (row,column,wordIndex) is not a reusable subproblem unless the used-cell set is also fixed. On board AAA / ABA, search for BAAAA, starting at B=(1,1). The branch (1,1)->(0,1)->(0,0) reaches index 2 but cannot finish: its only unused next A is (1,0), which is then trapped. The branch (1,1)->(1,0)->(0,0) reaches the same cell and word index, yet succeeds via (0,1)->(0,2). Caching the first failure under only (0,0,2) would wrongly reject the second branch. Clearing a cache between starting cells is insufficient because both branches share one start.

Count the output, not just the leaves

For keypad digits 79, there are 16 strings and each has two characters. A length-n output copy costs O(n); the total is O(nP), not merely O(P). Parentheses output similarly costs O(n Catalan(n)), and permutations cost O(n*n!). Exponential output is not an implementation defect, but it must be acknowledged. An existence query may stop early; an enumeration query must actually produce every required answer.

Reconstruction lab and answer key

Letter Combinations of a Phone Number

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".

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.

Combinations

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.

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.

Permutations

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?

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.

Combination Sum

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?

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.

Generate Parentheses

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?

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.

N-Queens II

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?

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.

Word Search

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?

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.

Problems in this module

• Letter Combinations of a Phone Number
• Combinations
• Permutations
• Combination Sum
• Generate Parentheses
• N-Queens II
• Word Search

Interactive checkpoint

Open the Backtracking quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable

Earlier-edition pattern links

The opening now derives the choices above before naming individual recipes. These headings preserve prior bookmarks.

Pattern A: Cartesian product expansion

Continue with the current reasoning workshop.

Pattern B: Combinations (choose / skip)

Continue with the current reasoning workshop.

Pattern C: Permutations

Continue with the current reasoning workshop.

Pattern D: Combination sum (reuse allowed)

Continue with the current reasoning workshop.

Pattern E: Balanced parentheses

Continue with the current reasoning workshop.

Pattern F: N-Queens with constraints

Continue with the current reasoning workshop.

Pattern G: Grid word search

Continue with the current reasoning workshop.

When to use Backtracking (checklist)

Continue with the current reasoning workshop.

Common failures (checklist)

Continue with the current reasoning workshop.

Problem mapping

Continue with the current reasoning workshop.