🧭 Master Roadmap to Problem Identification

🔹 1. Recursion Problems (Foundation)

Use recursion when a problem can be defined in terms of smaller self-similar subproblems with a clear base case.

A. Mathematical Recurrence

1. Factorial of n
2. Fibonacci numbers (naïve recursion)
3. Power of n (x^n) using recursion
4. Greatest Common Divisor (Euclidean algorithm)

B. Divide & Conquer

1. Binary Search
2. Merge Sort
3. Quick Sort
4. Maximum/Minimum in an array
5. Count inversions in an array

C. Recursion with Strings/Arrays

1. Reverse a string recursively
2. Palindrome check recursively
3. Print all subsequences of a string
4. Print all permutations of a string

D. Tree/Graph Recursion

1. Tree traversals (inorder, preorder, postorder)
2. Height/Depth of a binary tree
3. Count nodes in a binary tree
4. Lowest Common Ancestor (LCA) using recursion
5. DFS on a graph

🔹 2. Backtracking Problems (Branching + Choices + Undo)

Backtracking = Recursion + exploring multiple choices + pruning/undo when a choice doesn’t work.

A. Classic Backtracking

1. N-Queens problem
2. Rat in a Maze (all paths)
3. Knight’s Tour problem
4. Sudoku solver
5. Word Search in a grid

B. Subsets/Permutations/Combinations

1. Generate all subsets of a set
2. Generate all permutations of a string/array
3. Combination Sum (with/without duplicates)
4. Phone keypad letter combinations
5. Partition to K equal sum subsets

C. Constraint-Solving

1. Hamiltonian Path in a graph
2. Coloring a graph
3. Word break using backtracking
4. Crossword fill problem

🔹 3. Dynamic Programming Problems (Overlapping Subproblems + Optimal Substructure)

DP is recursion optimized with memoization/tabulation. Usually involves optimization: min, max, count, true/false.

A. 1D DP (Basic)

1. Fibonacci with memoization
2. Climbing Stairs (ways to reach top)
3. Min cost climbing stairs
4. House Robber problem
5. Jump Game (can reach end?)

B. Subset/Knapsack Problems

1. Subset Sum problem
2. Partition Equal Subset Sum
3. 0/1 Knapsack problem
4. Unbounded Knapsack
5. Coin Change (min coins / total ways)

C. String DP

1. Longest Common Subsequence (LCS)
2. Longest Common Substring
3. Edit Distance (Levenshtein)
4. Palindrome Partitioning (min cuts)
5. Regular Expression Matching

D. Grid/Matrix DP

1. Unique Paths in a grid
2. Minimum Path Sum
3. Maximal Square of 1s
4. Cherry Pickup problem
5. Gold Mine problem

E. Advanced DP

1. Longest Increasing Subsequence (LIS)
2. Longest Bitonic Subsequence
3. Matrix Chain Multiplication
4. Egg Dropping problem
5. Rod Cutting problem

• Stage 1 → Recursion: Solve problems until recursion feels natural (focus on base/recursive cases).
• Stage 2 → Backtracking: Pick problems with multiple choices & constraints.
• Stage 3 → DP: Start with recursive solutions → then optimize with memoization → then tabulation.

⚡ By mastering these ordered problem lists, you’ll instantly know:

• “This is recursion” → self-similar breakdown.
• “This is backtracking” → choices + pruning.
• “This is DP” → overlapping subproblems + optimization.