LeetCode · Backtracking
Backtracking Problem Set
Choose → explore → unchoose. Generate all valid combinations, permutations, and partitions. The key: define the decision tree and pruning conditions.
Concept page: Backtracking
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | subsets | LC 78 · Subsets | Include/exclude each element. 2ⁿ subsets. O(n · 2ⁿ). |
| Medium | subsets | LC 90 · Subsets II | Sort + skip duplicates at same level. O(n · 2ⁿ). |
| Medium | combination | LC 39 · Combination Sum | Unlimited reuse, start from current index onwards. O(2ⁿ). |
| Medium | combination | LC 40 · Combination Sum II | No reuse per index. Sort + skip duplicates at the same depth. O(2ⁿ). |
| Medium | permutation | LC 46 · Permutations | Swap-based or used-array approach. n! permutations. O(n · n!). |
| Medium | mapping | LC 17 · Letter Combinations of a Phone Number | Map digits to letters, backtrack through positions. O(4ⁿ). |
| Medium | grid | LC 79 · Word Search | DFS on grid with visited tracking. O(m · n · 4ᴸ). |
| Medium | partition | LC 131 · Palindrome Partitioning | Try every prefix, recurse on suffix if prefix is palindrome. O(n · 2ⁿ). |
| Hard | constraint | LC 51 · N-Queens | Place queen per row, check column + diagonals. O(n!). |