Key Patterns to Master
- Combinatorial Search: For generating subsets, permutations, and combinations.
- State Pruning: For stopping exploration of invalid branches early.
- Path Tracking: Maintaining the "current path" and undoing choices.
Hand-Picked Problems
| Problem | Difficulty | Key Pattern |
|---|---|---|
| Subsets | Medium | Power Set Generation |
| Permutations | Medium | Arrangement Logic |
| Combination Sum | Medium | Pruning |
| Word Search | Medium | Matrix Backtracking |
| Generate Parentheses | Medium | String Building |
| Letter Combinations of a Phone Number | Medium | Map-based Search |
| Palindrome Partitioning | Medium | String Splitting |
| Sudoku Solver | Hard | Constraint Satisfaction |
| N-Queens | Hard | 2D Constraints |
| Combination Sum III | Medium | Restricted Set |
Interview Tip
Always trace a small example (n=2) manually during the interview to ensure your backtrack logic correctly resets the state.