Recursion

Essential Recursion Practice Questions (No

DP)

MAXIMIZATION PROBLEMS
Beginner Level:
1. House Robber (LC 198) - max(rob(i-1), nums[i] + rob(i-2))

2. Maximum Path Sum in Binary Tree (LC 124) - Tree recursion

3. Maximum Depth of Binary Tree (LC 104) - Simple tree recursion

4. Diameter of Binary Tree (LC 543) - Max path through any node

Intermediate Level:
1. Binary Tree Maximum Path Sum (LC 124) - Complex tree traversal

2. Maximum Subarray Sum (LC 53) - max(nums[i], nums[i] + maxSubarray(i+1))

3. Best Time to Buy/Sell Stock (LC 121) - Track max profit recursively

4. Longest Increasing Subsequence (LC 300) - Include/exclude decisions

Advanced Level:
1. Cherry Pickup (LC 741) - Grid traversal with backtracking

2. Russian Doll Envelopes (LC 354) - 2D LIS with recursion

MINIMIZATION PROBLEMS

Recursion 1
 Beginner Level:
1. Minimum Depth of Binary Tree (LC 111) - Tree traversal

2. Climbing Stairs Cost (LC 746) - min(cost[i] + climb(i+1), cost[i] + climb(i+2))

3. Minimum Path Sum (LC 64) - Grid traversal with choices

4. Triangle Min Path (LC 120) - Choose left or right path

Intermediate Level:
1. Edit Distance (LC 72) - 3 choices: insert/delete/replace

2. Coin Change (LC 322) - min(1 + coinChange(amount - coin[i]))

3. Word Break (LC 139) - Try all prefix combinations

4. Palindrome Partitioning II (LC 132) - Min cuts needed

Advanced Level:
1. Burst Balloons (LC 312) - Interval-based recursion

2. Minimum Window Substring (LC 76) - Sliding window with recursion

3. Shortest Palindrome (LC 214) - String manipulation

COUNTING PROBLEMS
Beginner Level:
1. Climbing Stairs (LC 70) - count(n-1) + count(n-2)

2. Unique Paths (LC 62) - paths(m-1,n) + paths(m,n-1)

3. Unique Paths II (LC 63) - With obstacles

4. Fibonacci Numbers (LC 509) - Classic recursion

Intermediate Level:
1. Decode Ways (LC 91) - decode(i+1) + decode(i+2) with conditions

2. Target Sum (LC 494) - count(+nums[i]) + count(-nums[i])

Recursion 2
 3. Combination Sum (LC 39) - Include/exclude with repetition

4. Combination Sum IV (LC 377) - Order matters

5. Generate Parentheses (LC 22) - Count valid combinations

Advanced Level:
1. Unique Binary Search Trees (LC 96) - Catalan numbers

2. Number of Islands (LC 200) - DFS counting

3. Word Search II (LC 212) - Trie + DFS

BONUS: PATTERN RECOGNITION

When you see these keywords, think recursion:

"Maximum/Minimum ways" → Max/Min recursion

"Count number of ways" → Counting recursion

"All possible combinations" → Generate all (like your subsets)

"Optimal solution" → Choice-based recursion

"Tree/Grid traversal" → Structural recursion

Complete "Generate All Solutions"

Backtracking Problems
SUBSET/COMBINATION GENERATION

Recursion 3
 Core Problems:
1. Subsets (LC 78) - Generate all subsets

2. Subsets II (LC 90) - With duplicates

3. Combination Sum (LC 39) - Unlimited reuse

4. Combination Sum II (LC 40) - No reuse, with duplicates

5. Combination Sum III (LC 216) - Exactly k numbers, sum n

6. Combinations (LC 77) - Choose k from n numbers

Advanced Combinations:
1. Factor Combinations (LC 254) - All ways to factorize

2. Combination Sum IV (LC 377) - Order matters (though typically DP)

3. Letter Combinations of Phone Number (LC 17) - Phone keypad

4. Generate Parentheses (LC 22) - All valid parentheses

PERMUTATION GENERATION
Core Problems:
1. Permutations (LC 46) - All arrangements

2. Permutations II (LC 47) - With duplicates

3. Next Permutation (LC 31) - Generate next lexicographic

4. Permutation Sequence (LC 60) - kth permutation

String Permutations:
1. Letter Case Permutation (LC 784) - Toggle case combinations

2. Find All Anagrams (LC 438) - All permutations in string

3. Palindrome Permutation II (LC 267) - All palindromic permutations

STRING/BINARY GENERATION

Recursion 4
 Binary Strings:
1. Gray Code (LC 89) - Generate Gray code sequence

2. Binary Watch (LC 401) - All possible times

3. Letter Case Permutation (LC 784) - All case combinations

4. Flip Game II (LC 294) - All possible moves

String Generation:
1. Generate Parentheses (LC 22) - All balanced parentheses

2. Remove Invalid Parentheses (LC 301) - All valid by removing min

3. IP Addresses (LC 93) - All valid IP formations

4. Word Break II (LC 140) - All possible sentences

5. Palindrome Partitioning (LC 131) - All palindromic partitions

GRID/PATH GENERATION
Robot Paths:
1. Unique Paths (LC 62) - Count all paths (can generate too)

2. Unique Paths II (LC 63) - With obstacles

3. Path Sum II (LC 113) - All root-to-leaf paths with target sum

4. Binary Tree Paths (LC 257) - All root-to-leaf paths

Grid Exploration:
1. Word Search (LC 79) - Find if word exists

2. Word Search II (LC 212) - Find all words from dictionary

3. Surrounded Regions (LC 130) - All connected regions

4. Number of Islands (LC 200) - Count/find all islands

ADVANCED GENERATION PROBLEMS

Recursion 5
 Complex Backtracking:
1. N-Queens (LC 51) - All valid queen placements

2. N-Queens II (LC 52) - Count solutions

3. Sudoku Solver (LC 37) - Generate valid sudoku

4. Valid Sudoku (LC 36) - Check if valid

Game/Puzzle Generation:
1. Expression Add Operators (LC 282) - All ways to add operators

2. Different Ways to Add Parentheses (LC 241) - All ways to parenthesize

3. 24 Game (LC 679) - All ways to make 24

4. Strobogrammatic Number II (LC 247) - All n-digit strobogrammatic

Tree Generation:
1. Generate All Binary Trees (LC 95) - All BSTs with n nodes

2. All Possible Full Binary Trees (LC 894) - All full binary tree

BONUS: CREATIVE PROBLEMS

1. Matchsticks to Square (LC 473) - Partition into equal groups

2. Partition to K Equal Sum Subsets (LC 698) - Advanced partitioning

3. Beautiful Arrangement (LC 526) - Permutation with constraints

4. Flip Game (LC 293) - All possible next states

5. Android Unlock Patterns (LC 351) - All valid unlock patterns

6. Cracking the Safe (LC 753) - Shortest string containing all codes

7. Sequential Digits (LC 1291) - All numbers with sequential digits

Key Insight: Every "generate all" problem is just your subset template with
different:

Validation rules (when to add to result)

Recursion 6
 Choice generation (what options to try next)

State representation (what to track in recursion)

Your subset template is the Swiss Army knife of backtracking! Master it, and you
can solve 80% of these problems with minor modifications.

Things that are missing

If we were to be extremely pedantic and think about "all types of recursion" from a
computer science fundamentals perspective, one might also consider:

1. Basic Linear Recursion:

Examples: Factorial, sum of array elements, string reversal.

Your list implicitly assumes this foundation, as these are often building
blocks for more complex problems. It focuses more on problems where
recursion provides a strategic advantage for exploring search spaces.

2. Divide and Conquer (as a distinct pattern):

While many of your problems use divide-and-conquer implicitly (e.g., tree

problems, some array problems), explicitly naming it as a category with
classics like:

Merge Sort / Quick Sort (though these are sorting algorithms, their
recursive nature is key)

Maximum Subarray Sum (can be solved with D&C, though your

recurrence is more iterative/DP-like)

"Different Ways to Add Parentheses" (LC 241) is a good example

already on your list that fits D&C well.

Your current list focuses more on choice-based and exhaustive search

recursion than pure D&C for optimization where subproblems don't overlap
as much as in DP.

3. Mutual Recursion:

Recursion 7
 Where two or more functions call each other recursively. This is less
common in standard LeetCode problems but is a type of recursion. (e.g.,
parsers, state machines).

4. Tail Recursion:

A specific form where the recursive call is the very last operation. While
important for understanding compiler optimizations, it's more a
property of a recursive function than a problem type.

Recursion 8