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.

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.