Quick Comparison Table

Before diving deep, here's a quick reference to understand how these four paradigms differ. Bookmark this for quick revision!

One-Liner Definitions

How They Relate

                    RECURSION
                   (base technique)
                        │
          ┌─────────────┼─────────────┐
          │             │             │
          ▼             ▼             ▼
    BACKTRACKING       DP          GREEDY
    (+ pruning)    (+ caching)   (no exploration)
    (+ undo)

    "All valid      "Optimal      "One path,
     solutions"      answer"       fast"

Key Differences Explained

Let's understand the fundamental differences through the lens of the same problem: finding paths in a decision tree.

The Decision Tree Mental Model

Problem: Generate subsets of [1, 2]

                    []
                   /  \
            Include 1   Exclude 1
                /           \
              [1]            []
             /   \          /   \
       Inc 2   Exc 2   Inc 2   Exc 2
         /       \       /       \
      [1,2]     [1]    [2]       []

All leaf nodes = All subsets: [], [1], [2], [1,2]

Difference 1: What Gets Explored

Difference 2: Where the Answer Appears

Difference 3: Code Pattern

1void recurse(state) {
2    if (base_case) {
3        process_answer();  // Answer at leaf
4        return;
5    }
6    for (choice : choices) {
7        recurse(next_state);  // No undo
8    }
9}

1void backtrack(state, path) {
2    if (is_valid_solution(path)) {
3        collect_answer(path);  // Answer anywhere
4    }
5    for (choice : choices) {
6        if (is_valid(choice)) {   // Pruning
7            path.add(choice);     // Choose
8            backtrack(next_state, path);
9            path.remove(last);    // Undo ← KEY DIFFERENCE
10        }
11    }
12}

1int dp(state) {
2    if (base_case) return base_value;
3    if (memo[state] != -1) return memo[state];  // Cache hit
4
5    int result = combine(dp(subproblem1), dp(subproblem2));
6    memo[state] = result;  // Store ← KEY DIFFERENCE
7    return result;  // Answer bubbles to root
8}

1int greedy(input) {
2    sort_if_needed(input);
3    int answer = 0;
4
5    for (item : input) {
6        if (should_take(item)) {  // Local optimal
7            answer += item;       // Accumulate
8        }                         // No recursion, no undo
9    }
10    return answer;
11}

Difference 4: Same Problem, Different Questions

How to Identify the Right Approach

This is the most important section. Learn to recognize problem patterns and keywords that instantly reveal which paradigm to use.

Decision Flowchart

START: Read the problem
          │
          ▼
┌─────────────────────────────┐
│ Does it ask for ALL         │
│ combinations/permutations/  │──YES──▶ BACKTRACKING
│ subsets/paths?              │
└─────────────────────────────┘
          │ NO
          ▼
┌─────────────────────────────┐
│ Does it ask for COUNT or    │
│ OPTIMAL (min/max) value?    │──YES──┐
└─────────────────────────────┘       │
          │ NO                        ▼
          │              ┌─────────────────────────┐
          │              │ Are there OVERLAPPING   │
          │              │ subproblems?            │
          │              └─────────────────────────┘
          │                    │ YES        │ NO
          │                    ▼            ▼
          │                   DP      Plain Recursion
          ▼
┌─────────────────────────────┐
│ Can you prove local optimal │
│ = global optimal?           │──YES──▶ GREEDY
└─────────────────────────────┘
          │ NO
          ▼
    Consider DP or
    Brute Force

Keyword Recognition Guide

Problem Type → Approach

Quick Mental Tests

Interview Golden Rules

Constraints-Based Selection

The input size constraint is often the biggest hint about which approach will work. Learn to read constraints like a roadmap to the solution.

Constraint → Approach Mapping

Time Complexity Reference

Real Problem Examples

Common Pitfalls & Traps

Even experienced developers fall into these traps. Learn to recognize them before they cost you an interview or hours of debugging.

Pitfall 1: The Greedy Trap

Pitfall 2: DP vs Backtracking Confusion

Pitfall 3: Forgetting to Undo in Backtracking

1void backtrack(List<Integer> path) {
2    if (valid(path)) result.add(path);
3
4    for (int choice : choices) {
5        path.add(choice);
6        backtrack(path);
7        // Missing: path.remove(last)!
8    }
9}
10// Bug: path keeps growing forever

1void backtrack(List<Integer> path) {
2    if (valid(path)) {
3        result.add(new ArrayList<>(path));
4    }
5    for (int choice : choices) {
6        path.add(choice);      // Choose
7        backtrack(path);       // Explore
8        path.removeLast();     // Undo!
9    }
10}

Pitfall 4: Incomplete Memoization Key

1// WRONG: Only memoizing on index
2int solve(int index, int remaining) {
3    if (memo[index] != -1) return memo[index];
4    // Bug: Different 'remaining' values get same cached result!
5    ...
6}
7
8// CORRECT: Include all changing state
9int solve(int index, int remaining) {
10    if (memo[index][remaining] != -1) {
11        return memo[index][remaining];
12    }
13    ...
14}

Pitfall 5: Missing Overlapping Subproblems

Quick Reference: Avoid These Mistakes