💰 The Discovery Journey: Coin Change Problem
Let me walk you through the messy thinking process that leads to the solution, exactly as a designer would discover it.
This isn't a polished solution - it's the authentic struggle of understanding recursion and optimization.
Section 1: Discovery & Problem Understanding
1.1: Problem Analysis & Initial Thinking
First Attempt: Your Intuition (What You Got Right)
int func(int[] coins, int target, int numberOfCoinsUsed) {
if (target == 0) {
return numberOfCoinsUsed; // ✓ CORRECT INSTINCT
}
if (target < 0) {
// ??? You sensed something wrong happens here
}
for (int i = 0; i < length; i++) {
func(coins, target - coins[i], numberOfCoinsUsed++);
}
}
✓ "When I reach exactly the target, I should return how many coins I used"
✓ "Negative target means I went too far - this path is invalid"
✓ "I need to try every coin choice"
❓ "What does an invalid path return?"
❓ "How do I compare results from different paths?"
❓ "Where does the MIN operation happen?"
This confusion is THE KEY INSIGHT we need to unlock!
1.2: Thought Process & Strategy
How to Think About Recursion Returns
Step-by-step checklist:
1. Define what the function ASKS:
func(coins, 11) asks: "Minimum coins for amount 11?"
2. Define what the function RETURNS:
An integer: the answer to that question
3. Base cases return DIRECT answers:
target == 0 → Direct answer: 0 coins
target < 0 → Direct answer: "impossible" (use sentinel value)
4. Recursive case BUILDS answer from subproblems:
- Ask multiple subproblems (try each coin)
- Combine their answers (MIN operation)
- Add the "cost" of this step (+1 coin)
Resolving Common Confusions
Question 1: "Where to put MIN/MAX control?"
Answer: The MIN happens in the recursive case, AFTER collecting all subproblem results.
// ❌ WRONG: Trying to track minimum while recursing
for (int coin : coins) {
func(amount - coin, numberOfCoinsUsed++); // ✗ Lost information
}
// ✅ CORRECT: Ask subproblems, then combine answers
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int subAnswer = func(amount - coin); // Get the answer
minCoins = Math.min(minCoins, subAnswer + 1); // Compare answers
}
return minCoins; // Return OUR answer
When you call func(amount - coin, numberOfCoinsUsed++):
- You're not capturing the return value
- Each recursive call is independent - they can't see each other's results
- You have no way to compare and choose the minimum
The return value IS how subproblems communicate their answers!
Question 2: "What should it return?"
Mental model: Every function call is a QUESTION-ANSWER pair:
QUESTION: func(coins, 11) = "Min coins for 11?"
ANSWER: return 3 = "3 coins"
QUESTION: func(coins, -1) = "Min coins for -1?"
ANSWER: return MAX_VALUE = "Impossible"
The return value is not a side effect - it's the primary mechanism for communication in recursion!
Each level asks questions (recursive calls) and gets answers (return values), then uses those answers to build its own answer.
1.3: Prerequisites & Core Insights
The Critical "Aha!" Moment
In recursion, the return value IS the answer to "what's the minimum coins for THIS subproblem?"
Let me show you what this means:
// When you write:
func(coins, 11)
// You're asking: "What's the MINIMUM coins to make 11?"
// The RETURN VALUE is the answer!
// When recursion calls:
func(coins, 11 - 5) // which is func(coins, 6)
// You're asking: "What's the MINIMUM coins to make 6?"
// The RETURN VALUE tells you!
The Mental Shift:
❌ WRONG THINKING:
"I'll track
numberOfCoinsUsedas I go, and return it at the end"
✅ CORRECT THINKING:
"Each function call ASKS a question and RETURNS the answer. I ask about smaller subproblems, get their answers, and build my answer from theirs."
Section 2: Implementation & Deep Understanding
2.1: Solution Implementation
Step 1: What Should Invalid Paths Return?
Designer's thought process:
"If
target < 0, this path failed. What number represents FAILURE in a minimum problem?"
Think about the MIN operation:
Math.min(3, ???) // What should ??? be so it doesn't affect the result?
Answer: A very large number (or infinity)
if (target < 0) {
return Integer.MAX_VALUE; // "This path is impossible"
}
Because when we compare:
Math.min(3, Integer.MAX_VALUE) → 3 // Good path wins!
The failed path doesn't interfere with valid paths!
Step 2: Where Does the MIN Operation Happen?
The chronological discovery:
First Insight: "I try multiple coins, each gives a different answer"
int result1 = func(coins, target - coins[0]);
int result2 = func(coins, target - coins[1]);
int result3 = func(coins, target - coins[2]);
Second Insight: "I want the MINIMUM of all these results"
int best = Math.min(result1, Math.min(result2, result3));
Third Insight: "But I need to ADD 1 to account for the coin I just used!"
int best = Math.min(result1 + 1, result2 + 1, result3 + 1);
Step 3: The Complete Recursive Structure
int func(int[] coins, int target) {
// BASE CASE 1: Success - we made exact change
if (target == 0) {
return 0; // Zero coins needed to make zero
}
// BASE CASE 2: Failure - we overshot
if (target < 0) {
return Integer.MAX_VALUE; // Impossible path
}
// RECURSIVE CASE: Try every coin
int minCoins = Integer.MAX_VALUE; // Start with "impossible"
for (int coin : coins) {
int subproblemResult = func(coins, target - coin);
// If this path is valid, consider it
if (subproblemResult != Integer.MAX_VALUE) {
minCoins = Math.min(minCoins, subproblemResult + 1);
// ^^^^^^^^^^^^^^^^
// subproblem + current coin
}
}
return minCoins;
}
Complete Production-Ready Code
class Solution {
public int coinChange(int[] coins, int amount) {
int result = coinChangeHelper(coins, amount);
return result == Integer.MAX_VALUE ? -1 : result;
}
private int coinChangeHelper(int[] coins, int amount) {
// BASE CASE 1: Exact change made
if (amount == 0) {
return 0;
}
// BASE CASE 2: Overshot (invalid path)
if (amount < 0) {
return Integer.MAX_VALUE;
}
// RECURSIVE CASE: Try every coin choice
int minCoins = Integer.MAX_VALUE;
for (int coin : coins) {
int subResult = coinChangeHelper(coins, amount - coin);
// Only consider valid paths
if (subResult != Integer.MAX_VALUE) {
minCoins = Math.min(minCoins, subResult + 1);
}
}
return minCoins;
}
}
2.2: Key Concepts & Mechanics
Understanding the Critical Addition: Why + 1?
Why + 1?
Each recursive call tells us: "minimum coins needed for the remaining amount"
We need to add 1 to count the coin we just used to reduce the amount!
subproblemResult + 1
↑ ↑
remainder current coin
Reading the Code Like English
- "If I've made exact change" → return 0 (no more coins needed)
- "If I went negative" → return impossible (this path failed)
- "Otherwise, try every coin":
- Ask: "What's minimum for the remainder?"
- Add 1 for the coin I'm using now
- Keep track of the best option
- "Return the best option I found"
Why Two Functions?
Outer function (coinChange):
- Handles the conversion of MAX_VALUE to -1 (problem requirement)
- Clean interface for the caller
Inner function (coinChangeHelper):
- Pure recursive logic
- Uses MAX_VALUE as sentinel for impossible cases
2.3: Edge Cases & Validation
Test 1: Impossible Case
Input: coins = [2], amount = 3
Trace:
func([2], 3)
→ try coin 2: func([2], 1)
→ try coin 2: func([2], -1)
→ return MAX_VALUE // overshot
→ return MAX_VALUE
→ minCoins = MAX_VALUE
→ return MAX_VALUE // Final answer: -1
Sentinel values propagate up when no valid path exists.
The MAX_VALUE "bubbles up" through all the failed attempts, eventually reaching the top level where we convert it to -1.
Test 2: Multiple Paths
Input: coins = [1, 2, 5], amount = 11
Key decision point at func([1,2,5], 11):
// Path 1: Use coin 5
func(11 - 5) = func(6) → eventually returns 2
// So this path = 2 + 1 = 3
// Path 2: Use coin 2
func(11 - 2) = func(9) → eventually returns 3
// So this path = 3 + 1 = 4
// Path 3: Use coin 1
func(11 - 1) = func(10) → eventually returns 2
// So this path = 2 + 1 = 3
// MIN(3, 4, 3) = 3 ✓
The MIN operation naturally selects the optimal path.
We don't need to explicitly track which path is best - the MIN operation does it for us!
Section 3: Mastery & Visualization
3.1: Practical Examples/Visualization
Detailed Trace for coins = [1, 2, 5], amount = 11
Let me trace one complete path to show how the recursion works:
func(11)
├─ Try coin 5: func(6) + 1
│ ├─ Try coin 5: func(1) + 1
│ │ ├─ Try coin 5: func(-4) → MAX_VALUE
│ │ ├─ Try coin 2: func(-1) → MAX_VALUE
│ │ └─ Try coin 1: func(0) → 0
│ │ → min(MAX, MAX, 0+1) = 1
│ ├─ Try coin 2: func(4) + 1
│ │ └─ ... → returns 2
│ └─ Try coin 1: func(5) + 1
│ └─ ... → returns 1
│ → min(1+1, 2+1, 1+1) = 2
├─ Try coin 2: func(9) + 1
│ └─ ... → returns 3
├─ Try coin 1: func(10) + 1
│ └─ ... → returns 2
→ min(2+1, 3+1, 2+1) = 3 ✓
Interactive Understanding Questions
Q1: Why do we return 0 when amount == 0?
Click to reveal answer
Because we need zero coins to make zero amount.
This is both:
- Logically correct: No coins needed for no amount
- Mathematically correct: Doesn't add anything when we do
subResult + 1
If we returned 1 or any other value, we'd be adding extra coins that don't exist!
Q2: What if we used 0 instead of MAX_VALUE for invalid paths?
Click to reveal answer
Disaster! The MIN operation would always choose the invalid path:
Math.min(3, 0) = 0 // Wrong! 0 means "impossible", not "0 coins"
We'd return 0 for impossible cases, which the problem interprets as "success with 0 coins".
MAX_VALUE ensures invalid paths lose the MIN competition.
Q3: Why check subResult != Integer.MAX_VALUE before taking MIN?
Click to reveal answer
To prevent integer overflow!
Integer.MAX_VALUE + 1 = -2147483648 // Overflow! Wraps to negative
If we add 1 to MAX_VALUE, it wraps around to a huge negative number, which would win the MIN operation incorrectly!
By checking first, we avoid this overflow issue.
Q4: Can we solve this without recursion?
Click to reveal answer
Yes! That's what DP is for.
The recursive solution is top-down (starts at the goal, works to base cases).
We can convert it to bottom-up (starts at base cases, builds to goal):
// Bottom-up approach:
dp[0] = 0; // base case
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
Same logic, different direction!
3.2: Framework & Pattern Recognition
The Universal Recursion Pattern
This problem follows the same pattern as many DP problems:
| Problem | Decision at Each Step | How to Combine |
|---|---|---|
| Climbing Stairs | 1 step or 2 steps | Sum (counting paths) |
| Coin Change | Try each coin | Min (finding optimal) |
| Decode Ways | 1 digit or 2 digits | Sum (counting ways) |
// General structure:
func(state) {
if (base_case) return direct_answer;
best = initial_value;
for each choice:
result = func(new_state_after_choice);
best = combine(best, result + cost_of_choice);
return best;
}
Variables:
combine= min, max, sum, etc.cost_of_choice= what this decision costs (often 1)initial_value= MAX_VALUE for min, 0 for sum, etc.
Complexity Analysis - Pure Recursion
Time Complexity: O(amount^coins.length)
- At each level, we try all coins
- Maximum recursion depth is
amount(if we use coin=1 every time) - Exponential time due to overlapping subproblems
Space Complexity: O(amount)
- Recursion stack depth in worst case
For coins = [1, 2, 5] and amount = 100:
- We'll compute
func(50)many times from different paths - This is where memoization comes in!
The pure recursive solution has exponential time complexity - we need DP optimization!
3.3: Key Takeaways & Summary
Core Insights
- ✅ Return values are answers - Not side effects, but the primary communication mechanism
- ✅ Sentinel values represent impossibility - MAX_VALUE for MIN problems, -1 or MIN_VALUE for MAX problems
- ✅ Base cases return direct answers - No recursion needed when you know the answer
- ✅ Recursive cases build from subproblems - Ask smaller questions, combine answers
- ✅ The +1 represents the current decision - Add the cost of the choice you're making
Recursion is about asking questions and building answers from smaller questions.
func(amount) asks: "Min coins for this amount?"
↓
Asks smaller questions: "Min coins for amount - coin?"
↓
Gets answers: subResult
↓
Builds own answer: min(all subResults) + 1
↓
Returns answer to whoever asked
Master this thinking pattern, and hundreds of DP problems become approachable!
Next Steps in the Journey
Now that you understand the recursive foundation:
- Add Memoization - Cache results to eliminate redundant computation
- Convert to Bottom-Up - Iterative DP for better space efficiency
- Optimize Space - Notice we only need recent values
- Master the Pattern - Apply to similar unbounded knapsack problems
Pure Recursion (Understand the structure)
↓
Top-Down with Memo (Eliminate redundant work)
↓
Bottom-Up DP (Remove recursion overhead)
↓
Space-Optimized (Minimize memory usage)
You now have the foundation! Each optimization builds on this recursive understanding.
Ready for Optimization?
The next doc will show you memoization and bottom-up DP - same logic, but 1000x faster!
Would you like to see how we transform this O(amount^coins) solution into O(amount × coins)?