Tags
- ⭐ = solved in first try
- 📍 = revisit
- 🔥 = important
- ⚠️ = solved but edge case missed
- 👀 = solved but had to see little solution first
- 🐢 = solved, but less optimized
- 💀 = out of the box
- no tag = pending/not started
6. Pattern: Backtracking
6.1 Subsets / Power Set
💡 Signal: “all subsets”, “power set”, “all subsequences”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Subsets (medium) | No base case needed — add current at every node | ||
| 2. Subsets II (medium) | Sort + skip if (i > start && nums[i] == nums[i-1]) |
6.2 Combinations / Combination Sum
💡 Signal: “all combinations”, “combination sum”, “k numbers that sum to target”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Combinations (medium) | Same as subsets but stop when current.size() == k | ||
| 2. Combination Sum (medium) | Pass i (not i+1) to allow reuse of same element | ||
| 3. Combination Sum II (medium) | Sort + skip dupes + pass i+1 (no reuse) | ||
| 4. Combination Sum III (medium) | k numbers from 1-9 summing to n. Pass i+1, no reuse |
6.3 Permutations
💡 Signal: “all permutations”, “all arrangements”, “order matters”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Permutations (medium) | Swap approach or visited array. Loop starts at 0 not start | ||
| 2. Permutations II (medium) | Sort + skip if (i > 0 && nums[i]==nums[i-1] && !used[i-1]) | ||
| 3. Permutation Sequence (hard) | Math — factorial number system, not backtracking | ||
| 4. Letter Case Permutation (medium) | Branch on alpha chars: lower or upper. Digits → no branch |
6.4 Partitioning
💡 Signal: “partition string”, “split into palindromes”, “all ways to split”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Palindrome Partitioning (medium) | At each index try all substrings. Only recurse if palindrome | ||
| 2. Restore IP Addresses (medium) | 4 segments, each 1-3 digits, value 0-255, no leading zeros |
6.5 Grid / Board Search
💡 Signal: “word search”, “path in grid”, “explore all paths”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Word Search (medium) | DFS + mark visited in-place. Backtrack by restoring cell | ||
| 2. Unique Paths III (hard) | Visit every non-obstacle cell exactly once. Count valid paths | ||
| 3. Path with Maximum Gold (medium) | DFS from every non-zero cell. Track max gold collected |
6.6 Constraint Satisfaction (N-Queens / Sudoku)
💡 Signal: “place N queens”, “solve sudoku”, “valid arrangement under constraints”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. N-Queens (hard) | Row by row. Check col, left-diag, right-diag for conflicts | ||
| 2. N-Queens II (hard) | Same as N-Queens but just count solutions | ||
| 3. Sudoku Solver (hard) | Try 1-9 in each empty cell. Check row, col, 3×3 box | ||
| 4. Beautiful Arrangement (medium) | `i % pos == 0 |
6.7 String Generation
💡 Signal: “generate parentheses”, “letter combinations”, “happy strings”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Generate Parentheses (medium) | Two choices: ( if open < n, ) if close < open | ||
| 2. Letter Combinations of a Phone Number (medium) | Map digit→letters. For each digit, branch on all its letters | ||
| 3. Happy Strings (medium) | Adjacent chars can’t be same. Early stop at k results | ||
| 4. Count Number of Texts (medium) | Similar to phone number but needs memoization (DP) |
6.8 Optimization / Selection
💡 Signal: “fair distribution”, “maximum score”, “maximum compatibility”
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Fair Distribution of Cookies (medium) | Distribute bags to k children. Minimize max. Prune early | ||
| 2. Maximum Score Words Formed by Letters (hard) | Subset selection with letter budget constraint | ||
| 3. Maximum Compatibility Score Sum (medium) | Assign students to mentors. Permutation matching | ||
| 4. Shopping Offers (medium) | Try each offer if valid, recurse with reduced needs |