Backtracking

Backtracking explores a decision tree one choice at a time. The core skill is managing the mutable path: choose, recurse, then undo exactly that choice. Pruning matters when the decision tree is large.

Verbally reusable template:

1. Choose append into the live path (candidate).
2. Explore recurse with tightened constraints (startIdx, remaining sum, occupancy mask).
3. Unchoose undo the mutation before trying the sibling branch.

If recursion returns without restoring shared state (pop, backtrack bitmask), correctness breaks silently. Sorting duplicates + skipping equal neighbors is the canonical way to avoid duplicate combinations.

Quick Identifier

• Topic: backtracking
• Pattern: DFS enumeration, choose/undo recursion, dedupe after sorting, or constraint pruning.
• Core Question: Are we asked to produce all valid combinations, permutations, partitions, or placements?

Quick Sights

• Typical Time Complexity: Exponential or factorial, scaled by the output size.
• Typical Space Complexity: O(depth) recursion plus output storage.
• Core Mechanism: Maintain a partial path, try one legal choice, recurse, then undo before trying the next choice.

Diagram

Recognition Cues

• All subsets, combinations, permutations, partitions, or board placements.
• Need to avoid duplicate outputs after sorting.
• Constraint satisfaction like N-Queens or word search.

Problem List

Start with 078. Subsets, 039. Combination Sum, 046. Permutations, 079. Word Search, and 051. N-Queens.