2.2 Algorithm Selection: Greedy vs Dynamic Programming vs Backtracking
Choosing between Greedy, Dynamic Programming (DP), and Backtracking is one of the most critical decisions in problem-solving. Each approach has distinct characteristics, use cases, and trade-offs. Understanding when to use each is essential for efficient algorithm design.
2.2.1 Core Differences
| Aspect | Greedy | Dynamic Programming | Backtracking |
|---|---|---|---|
| Goal | Find one optimal solution via local choices | Find optimal value (min/max/count) | Find all solutions or one valid solution |
| Question Type | “What is the optimal strategy?” | “What is the minimum/maximum?” | “What are all possible combinations?” |
| Example Question | “Capture every price increase?” | “Minimum coins to make amount?” | “All ways to make amount?” |
| Decision Making | Local optimal choice → Global optimum | Optimal substructure with overlapping subproblems | Exhaustive search with pruning |
| Reconsiders Choices | Never - choices are irrevocable | Implicitly via memoization/tabulation | Always - tries all possibilities |
| Overlapping Subproblems | Not applicable (no subproblems) | Required - reuses computed results | May exist but not exploited |
| State Storage | None (stateless decisions) | Stores results of subproblems | Stores current path/state |
| Time Complexity | Linear to \(O(n \log n)\) | Polynomial (typically \(O(n \times m)\)) | Exponential (typically \(O(b^d)\) or \(O(n!)\)) |
| Space Complexity | \(O(1)\) to \(O(n)\) | \(O(n)\) to \(O(n \times m)\) | \(O(d)\) recursion stack |
| Optimization Technique | Greedy choice property | Optimal substructure + memoization | Pruning invalid paths |
| Returns | One optimal solution | Single value (number, boolean) | List of all solutions or single path |
| Proof Required | Yes - must prove greedy works | No (correctness follows from recurrence) | No (exhaustive search guarantees correctness) |
2.2.2 Key Insight: Local vs Global vs Exhaustive
The fundamental differences:
- Greedy: “Make the best local choice now” (assumes local optimum → global optimum)
- DP: “What is the best global value?” (builds optimal solution from subproblems)
- Backtracking: “What are all possible ways?” (explores entire solution space)
2.2.3 When to Use Greedy
Use Greedy when the problem has the greedy choice property: making locally optimal choices leads to a globally optimal solution.
Critical Requirement: You must prove that the greedy strategy works (via exchange argument, contradiction, or induction). If greedy fails, use DP instead.
Greedy Question Patterns: - “Maximize/minimize by making optimal choices at each step” - Problems where choices don’t conflict with each other - No dependencies between choices (future choices don’t depend on past ones)
Examples:
| Problem | Greedy Strategy | Why Greedy Works? |
|---|---|---|
| Stock II | Capture every price increase | No conflicts - all increases are independently profitable |
| Activity Selection | Pick activity with earliest finish time | Leaves maximum room for future activities |
| Huffman Coding | Merge two smallest frequency nodes | Proven optimal by exchange argument |
| Fractional Knapsack | Take items by value/weight ratio | Can take fractions - greedy maximizes value |
When Greedy FAILS:
- Stock Cooldown: Selling today forces rest tomorrow (choices conflict) → Use DP
- 0/1 Knapsack: Can’t take fractions, greedy by ratio fails → Use DP
- Coin Change (minimum coins): Greedy by largest coin first fails for [1,3,4], target 6 → Use DP
How to Verify Greedy Works: 1. Try counterexamples - If you find one where greedy fails, use DP 2. Prove via exchange argument - Show swapping greedy choice with another makes solution worse 3. Check for conflicts - Do current choices block better future choices?
2.2.4 When to Use Dynamic Programming
Use DP when the problem asks for an optimal value or count, and exhibits:
- Optimal Substructure: Solution to the problem can be built from solutions to subproblems
- Overlapping Subproblems: Same subproblem is solved multiple times
DP Question Patterns: - “Find the minimum/maximum …” - “Count the number of ways …” - “Is it possible to reach …?” (when combined with optimization) - “What is the longest/shortest …?”
Examples:
| Problem | Question | Why DP? |
|---|---|---|
| Coin Change | Minimum coins to make amount? | Asks for minimum count |
| Climbing Stairs | How many ways to reach top? | Asks for total count of ways |
| Longest Increasing Subsequence | Length of longest subsequence? | Asks for maximum length |
| 0/1 Knapsack | Maximum value with weight limit? | Asks for maximum value |
| House Robber | Maximum money without alerting? | Asks for maximum sum |
| Minimum Plans (HackerRank) | Minimum plans to reach bandwidth? | Asks for minimum count |
Common DP Patterns: - Unbounded Knapsack: Unlimited use of items (Coin Change, Minimum Plans) - 0/1 Knapsack: Each item used at most once - Longest/Shortest Path: In DAGs or grids - Counting Ways: Climbing Stairs, Unique Paths
2.2.5 When to Use Backtracking
Use Backtracking when the problem asks for all solutions or one valid path, requiring exhaustive search:
Backtracking Question Patterns: - “Find all combinations that …” - “Generate all permutations …” - “Return all valid arrangements …” - “List all subsets …” - “Find any path that satisfies …”
Examples:
| Problem | Question | Why Backtracking? |
|---|---|---|
| Combination Sum | All combinations summing to target? | Asks for all solutions |
| Permutations | All permutations of array? | Asks for all arrangements |
| Subsets | All possible subsets? | Asks for all subsets |
| N-Queens | All valid queen placements? | Asks for all valid boards |
| Word Search | Does path exist in grid? | Asks for path existence |
| Index Combinations (HackerRank) | All index combinations for target? | Asks for all combinations |
Common Backtracking Patterns: - Choose-Explore-Unchoose: Combinations, subsets - Permutations: Track used elements - Grid/Graph Traversal: Mark-unmark visited cells
2.2.6 The Critical Distinction: Same Problem, Different Questions
How you frame the question determines which algorithm to use. Consider these examples:
2.2.6.1 Example 1: Stock Trading
| Question | Approach | Answer | Why? |
|---|---|---|---|
| “Maximum profit with unlimited transactions?” | Greedy | Sum all price increases | No conflicts - capture every gain |
| “Maximum profit with cooldown?” | DP | Track states (hold/sold/rest) | Choices conflict - selling blocks buying |
| “All transaction sequences for profit \(\ge\) X?” | Backtracking | List all valid sequences | Need all solutions |
2.2.6.2 Example 2: Coin Change
Consider coins = [1, 2, 5] and target = 5:
| Question | Approach | Answer | Why? |
|---|---|---|---|
| “Minimum coins to make 5?” | DP | 2 (use coin 5, or coins 2+3) |
Asks for optimal count |
| “Can greedy (largest first) work?” | No | Fails for [1,3,4], target 6 |
Greedy gives [4,1,1]=3, optimal is [3,3]=2 |
| “All ways to make 5?” | Backtracking | [[1,1,1,1,1], [1,1,1,2], [1,2,2], [5]] |
Must enumerate all solutions |
| “Number of ways to make 5?” | DP | 4 |
Count without listing |
2.2.6.3 Example 3: Activity Selection
| Question | Approach | Answer | Why? |
|---|---|---|---|
| “Maximum non-overlapping activities?” | Greedy | Pick earliest finish time | Greedy choice property proven |
| “All valid schedules?” | Backtracking | List all combinations | Need all solutions |
Key Observations: - Greedy: Works when local choices don’t conflict → Fast (\(O(n \log n)\)) - DP: Works when choices conflict but exhibit optimal substructure → Moderate (\(O(n^2)\)) - Backtracking: Necessary when you need all solutions → Slow (\(O(2^n)\))
2.2.7 Hybrid Cases: DP with Path Reconstruction
Sometimes you need both the optimal value AND the actual solution:
Example: “Find the minimum coins AND which coins to use”
Approach: DP + Path Reconstruction 1. Use DP to find the optimal value 2. Backtrack through the DP table to reconstruct the solution
// Step 1: DP to find minimum
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// Step 2: Reconstruct the solution
List<Integer> result = new ArrayList<>();
int current = amount;
while (current > 0) {
for (int coin : coins) {
if (current >= coin && dp[current - coin] == dp[current] - 1) {
result.add(coin);
current -= coin;
break;
}
}
}This is NOT pure backtracking because we don’t enumerate all solutions—we reconstruct one optimal solution from the DP table.
2.2.8 Overlapping Subproblems: The Deciding Factor
Without Memoization, backtracking can be extremely inefficient for optimization problems:
Example: Minimum coins for amount 11 with coins [1, 5]
Backtracking (without memo):
minCoins(11) calls:
minCoins(10) + 1 [using coin 1]
minCoins(9) + 1
minCoins(8) + 1
... (exponential explosion)
minCoins(6) + 1 [using coin 5]
minCoins(5) + 1
minCoins(4) + 1 ← Recalculates minCoins(4) again!
...
With DP:
dp[0] = 0
dp[1] = 1
dp[2] = 2
...
dp[4] = 4 ← Calculated once, reused
...
dp[11] = 3When Overlapping Subproblems Exist: - For optimization → Use DP (polynomial time) - For enumeration → Backtracking is necessary (exponential but unavoidable)
2.2.9 Decision Tree
┌────────────────────────────────┐
│ Start: Understand the problem │
└──────────────┬─────────────────┘
│
┌──────────────┴─────────────┐
│ Does it ask for ALL │
│ solutions/combinations? │
└──────┬──────────────┬──────┘
│ │
YES NO
│ │
▼ │
┌──────────────┐ │
│ Backtracking │ │
│ │ │
│ O(b^d), O(n!)│ │
└──────────────┘ │
│
┌──────────────┴────────────┐
│ Does it ask for optimal │
│ value (min/max/count)? │
└──────┬──────────────┬─────┘
│ │
YES NO
│ │
┌──────────────┴──────┐ │
│ Can you make local │ │
│ optimal choices │ │
│ without conflicts? │ │
└──────┬──────────┬───┘ │
│ │ │
YES NO │
│ │ │
▼ ▼ ▼
┌───────────┐ ┌──────────┐ ┌──────────┐
│ Greedy │ │ DP │ │ Other │
│ │ │ │ │(Two Ptr, │
│ O(n logn) │ │ O(n×m) │ │ MinMax) │
└───────────┘ └──────────┘ └──────────┘
↑ ↑
│ │
Must PROVE Has optimal
it works! substructure +
overlapping
subproblemsDecision Steps:
Need ALL solutions? → Backtracking
- Example: All permutations, all subsets, all combinations
Need ONE optimal value? → Check greedy first, then DP
Try Greedy:
- Can you make locally optimal choices?
- Do choices conflict with each other?
- Can you PROVE greedy works?
If YES → Use Greedy If NO → Use DP
Use DP if:
- Choices have dependencies
- Overlapping subproblems exist
- Optimal substructure present
Neither optimization nor enumeration? → Other techniques
- Two Pointers, MinMax, Sliding Window, etc.
2.2.10 Common Mistakes
1. Using Greedy When It Doesn’t Work
// ❌ WRONG: Greedy for 0/1 Knapsack
// Take items by value/weight ratio - FAILS!
Arrays.sort(items, (a,b) -> (b.value/b.weight) - (a.value/a.weight));
int totalValue = 0;
for (Item item : items) {
if (item.weight <= capacity) {
totalValue += item.value;
capacity -= item.weight;
}
}
// Counterexample: items=[(60,10), (100,20), (120,30)], capacity=50
// Greedy: takes (60,10) + (100,20) = 160, leaves 20 capacity wasted
// Optimal: takes (100,20) + (120,30) = 220// ✅ CORRECT: Use DP for 0/1 Knapsack
int[][] dp = new int[n+1][capacity+1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
if (items[i-1].weight <= w) {
dp[i][w] = Math.max(dp[i-1][w],
items[i-1].value + dp[i-1][w - items[i-1].weight]);
} else {
dp[i][w] = dp[i-1][w];
}
}
}
// Time: O(n × capacity) - Guaranteed optimal2. Using Backtracking for Optimization Problems
// ❌ WRONG: Using backtracking to find minimum coins
int minCoins = Integer.MAX_VALUE;
void backtrack(int[] coins, int remaining, int count) {
if (remaining == 0) {
minCoins = Math.min(minCoins, count);
return;
}
for (int coin : coins) {
if (coin <= remaining) {
backtrack(coins, remaining - coin, count + 1);
}
}
}
// Time: O(n^m) - Exponential, recalculates subproblems// ✅ CORRECT: Using DP for optimization
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// Time: O(n × m) - Polynomial, solves each subproblem once2. Using DP for Enumeration Problems
2.2.11 Summary Table: Which Algorithm for Which Problem?
| Problem Type | Example | Algorithm | Complexity |
|---|---|---|---|
| Optimal with Independent Choices | Stock II (unlimited trades) | Greedy | \(O(n)\) to \(O(n \log n)\) |
| Optimal with Conflicting Choices | Stock Cooldown | DP | \(O(n)\) to \(O(n \times m)\) |
| Minimum/Maximum Value | Minimum coins for amount | DP | \(O(n \times m)\) |
| Count Ways (no enumeration) | Number of paths in grid | DP | \(O(n \times m)\) |
| All Combinations | All subsets of array | Backtracking | \(O(2^n)\) |
| All Permutations | All orderings of array | Backtracking | \(O(n!)\) |
| Path Exists (simple) | Can reach target sum? | DP (boolean) | \(O(n \times m)\) |
| All Paths | All paths to target sum | Backtracking | \(O(b^d)\) |
| Longest/Shortest Sequence | Longest increasing subsequence | DP | \(O(n^2)\) or \(O(n \log n)\) |
| Generate All Sequences | All valid parentheses | Backtracking | \(O(4^n / \sqrt{n})\) |
| Tracking Min/Max | Best Time to Buy Stock I | MinMax | \(O(n)\) |
2.2.12 Key Takeaway
Ask yourself these questions in order:
- “Does it ask for ALL solutions?”
- YES → Backtracking (no choice - must enumerate)
- NO → Continue to question 2
- “Does it ask for an optimal value?”
- NO → Other techniques (Two Pointers, MinMax, etc.)
- YES → Continue to question 3
- “Can I make locally optimal choices without conflicts?”
- YES and can PROVE it → Greedy (fastest)
- NO (choices conflict) → DP (moderate)
- UNSURE → Try counterexample: if greedy fails → DP
- “What does the problem return?”
int,boolean,long→ Likely Greedy or DPList<List<...>>→ Likely Backtracking
Decision Priority: 1. Greedy (if applicable) - Try first, fastest 2. DP (if greedy fails) - Handles complex dependencies 3. Backtracking (if need all solutions) - Last resort, slowest