Backtracking [mp]

Micro pattern¶

Description¶

Build candidates incrementally, recursively explore each choice, and undo mutable state before trying the next choice.

Problems¶

Cartesian choices¶

Choose one option at each position from the available alternatives.

• 17. Letter Combinations of a Phone Number (Top Medium)
• 46. Permutations (Top Medium)
• 78. Subsets (Top Medium)
• 1079. Letter Tile Possibilities (Google Prep)

Constrained generation¶

Explore only choices that can preserve a valid partial result.

• 22. Generate Parentheses (Top Medium)
• 131. Palindrome Partitioning (Top Hard)
• 301. Remove Invalid Parentheses (Top Hard)

Grid paths¶

Temporarily mark cells so the current path cannot reuse them.

• 79. Word Search (Top Medium)
• 212. Word Search II (Top Hard)

Graph paths¶

Append a neighbor to the current path and remove it after exploring that branch.

• 797. All Paths From Source to Target (Graph Theory)