README.md

09 - Recursion + Backtracking

PHASE 9 — RECURSION + BACKTRACKING (431–450)

Topics Covered

• Subset and Combination Generation
• Permutation and Duplicate Handling
• Grid Search and Constraint Solving
• Parentheses and Partition Backtracking
• State Pruning and Branch Ordering

---

Problems List

No.	Problem	Difficulty	Topics	Link
1	Subsets	Medium	Backtracking, Recursion	Open
2	Combination Sum	Medium	Backtracking, Recursion	Open
3	Combination Sum II	Medium	Backtracking, Recursion	Open
4	Permutations	Medium	Backtracking, Recursion	Open
5	Permutations II	Medium	Backtracking, Recursion	Open
6	Word Search	Medium	Backtracking, Grid	Open
7	Palindrome Partitioning	Medium	Backtracking, String	Open
8	Letter Combinations of Phone Number	Medium	Backtracking, String	Open
9	Generate Parentheses	Medium	Backtracking, String	Open
10	Restore IP Addresses	Medium	Backtracking, String	Open
11	Rat in a Maze	Medium	Backtracking, Grid	Open
12	Combination Sum III	Medium	Backtracking, Recursion	Open
13	Beautiful Arrangement	Medium	Backtracking, Permutation	Open
14	Matchsticks to Square	Medium	Backtracking, Partition	Open
15	Fair Distribution of Cookies	Medium	Backtracking, Partition	Open
16	Partition to K Equal Sum Subsets	Medium	Backtracking, Partition	Open
17	N-Queens	Hard	Backtracking, Constraint	Open
18	Sudoku Solver	Hard	Backtracking, Constraint	Open
19	M-Coloring Problem	Hard	Backtracking, Graph	Open
20	Expression Add Operators	Hard	Backtracking, String	Open

---

Important Patterns

Subsets and Combinations

• Decide for each element whether to include it or skip it
• Sort first when duplicate handling matters
• Use start indices to avoid revisiting earlier choices

Permutations

• Track used elements with a visited array or in-place swapping
• Skip duplicates by sorting and checking previous equal values
• Build the answer incrementally and backtrack after exploring each branch

Grid and Constraint Search

• Mark cells as visited before exploring neighbors
• Undo state changes on return to keep branches independent
• Prune early when constraints are violated

String Construction Problems

• Build partial strings or expressions one decision at a time
• Validate feasibility before deeper recursion
• Use pruning to reduce the branching factor