Recursion & Backtracking problems, grouped by pattern
Backtracking explores every choice, undoes it, and tries the next. Learn the pick / not-pick tree once and subsets, combinations, permutations, N-Queens and word search become variations on the same template.
When to reach for it
- Generate all subsets, combinations or permutations
- Place items on a board under constraints
- The answer is a list of all valid configurations
Mistakes to watch for
- Adding the shared path list instead of a copy
- Skipping duplicates at every depth instead of among siblings
- Not restoring state after the recursive call
The 38 problems
1Basic Recursion
- Factorial of a number Animated Easy
- Fibonacci Number Animated Easy
- Binary Tree Inorder Traversal (Recursive) Animated Easy
- Basic Backtracking Template Animated Medium
- Binary Tree Paths Animated Easy
- Nested List Weight Sum II Medium
- Nested List Weight Sum Medium
22D Matrix
- N-Queens Animated Hard
3Pick / Not-Pick
- Generate all binary strings without consecutive 1's Learn how to skip indices in recursion Animated Medium
- Subsets (2 choices per element) Animated Medium
- Subsets II Learn how to handle duplicates Animated Medium
- Combinations Animated Medium
- Combination Sum (repeating elements) Animated Medium
- Combination Sum II Animated Medium
- Combination Sum III homework Animated Medium
- Generate Parentheses Medium
- Partition to K Equal Sum Subsets Medium
- Matchsticks to Square Medium
- Maximum Length of a Concatenated String with Unique Characters Medium
4Permutations
- Permutations - Swap Trick Animated Medium
- Permutations Animated Medium
- Permutations II Animated Medium
- Verbal Arithmetic Puzzle Hard
52D Matrix Backtracking
- Word Search Animated Medium
- Robot Room Cleaner Hard
- Sudoku Solver Hard
6Choice per Position
- Letter Combinations of a Phone Number Medium
- Confusing Number II Hard
- Strobogrammatic Number II Medium
- Palindrome Partitioning Medium
- Brace Expansion Medium
- Pyramid Transition Matrix Medium
- Restore IP Addresses Medium
- Word Break II Hard
7Divide and Conquer
- Construct Quad Tree Medium
- Special Binary String Hard