What you'll learn
Quick Answer
The coin change problem is really two different problems that share a name. The first asks for the minimum number of coins to reach an amount, solved with a DP recurrence that takes a min() over coin choices. The second asks how many distinct ways there are to reach an amount, and it needs coins in the outer loop and amount in the inner loop — swap that order and you silently count ordered permutations instead of combinations, inflating the answer. Both are demonstrated and verified below against brute force, with the exact wrong number the bug produces.
Two Problems, One Name
"The coin change problem" gets used for two different questions that happen to share coins and an amount as inputs, and nothing else structurally:
- Minimum coins: given coin denominations and a target amount, what's the fewest coins that sum to it?
- Number of ways: given the same inputs, how many distinct combinations of coins sum to it (order doesn't matter — three 1s and a 2 is one combination, not several)?
Both are solved with dynamic programming, and both build a 1D array indexed by amount. That surface similarity is exactly what causes bugs: it's easy to assume the loop structure that works for one works for the other. It doesn't. The first uses min() and is loop-order-independent. The second sums counts, and gets the loop order wrong in exactly the way this article demonstrates, on real numbers, below.
Variant 1: Minimum Coins
The recurrence: to make amount a with the fewest coins, try every coin c ≤ a, and take 1 plus whatever the fewest coins is for the remaining amount a - c. Take the best option across all coins.
function minCoinsDP(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a && dp[a - c] + 1 < dp[a]) {
dp[a] = dp[a - c] + 1;
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}Run against a memoized brute-force recursive version on real inputs, printed directly from the executed script:
coins=[1,5,10,25] amount=63: DP=6 brute=6 [MATCH]
coins=[1,3,4] amount=6: DP=2 brute=2 [MATCH]
coins=[2,5] amount=11: DP=4 brute=4 [MATCH]
coins=[3,7] amount=5: DP=-1 brute=-1 [MATCH]63 cents with US coins takes 6: two quarters, one dime, three pennies. The last row is worth noting — with only 3-cent and 7-cent coins, amount 5 is genuinely impossible, and both implementations correctly return -1 instead of a wrong number.
Variant 2: Counting the Ways
Counting distinct combinations needs a different recurrence and, critically, a different loop order. The correct version puts coins in the outer loop, amount in the inner loop:
function countWaysCorrect(coins, amount) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const c of coins) {
for (let a = c; a <= amount; a++) {
dp[a] += dp[a - c];
}
}
return dp[amount];
}Why coins-outer matters: fully processing one denomination before moving to the next means each combination gets built in a fixed, canonical coin order — you can never reach the same combination through two different orderings, so it's counted exactly once. This is the part that's easy to get backwards, and the next section shows exactly what happens when you do.
The Bug: Swapping the Loop Order Overcounts
Swap the two loops — amount outer, coins inner — and the code still runs and still returns a number. That number is wrong:
function countWaysBuggy(coins, amount) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (let a = 1; a <= amount; a++) {
for (const c of coins) {
if (c <= a) dp[a] += dp[a - c];
}
}
return dp[amount];
}Run both against a brute-force count of actual combinations, for coins [1, 2, 5] and amount 5, printed directly from the executed script:
countWaysCorrect: 4
countWaysBuggy (amount-outer): 9
brute force combinations: 4
brute force ORDERED sequences: 9The buggy version returns 9, and 9 is not a random wrong number — it's the exact count of ordered sequences of coins summing to 5 (1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1, 5). The amount-outer loop lets every ordering of the same coins get counted separately, because by the time it reaches amount a it has no memory of which coin was used last. It silently answers a different, related question instead of the one you asked.
Verifying Both Variants Against Brute Force
Running all three implementations across multiple coin sets confirms the pattern holds, not just for one lucky example:
coins=[1,2,5] amount=5: CORRECT=4 BUGGY=9 brute-combinations=4
coins=[2,3,5] amount=8: CORRECT=3 BUGGY=6 brute-combinations=3
coins=[1,5,10] amount=12: CORRECT=4 BUGGY=18 brute-combinations=4The correct, coins-outer version matches brute-force combinations every time. The buggy, amount-outer version overcounts every time, and the size of the overcount grows with how many orderings each combination has — for [1,5,10] and amount 12, it's off by more than 4x. This is the kind of bug that passes a single hand-checked test case and then fails silently in production on any input with more than one way to make change. It's also worth testing this way rather than eyeballing the code, because both versions look equally plausible on a read-through — the bug is invisible until you check the actual returned number against something independently correct.
When to Use Which
Use minimum coins when the real question is "what's the fewest units to reach a target" — vending machine change, resource allocation with discrete units, or any interview question phrased around minimizing count.
Use the counting-ways variant when the question is about how many distinct combinations exist — this comes up in combinatorics problems and any "how many ways can you partition this" question with a fixed set of parts.
If you only remember one thing: whenever a DP problem involves both a set of items (coins) and a target (amount), ask whether the order of picking items should matter to the answer. If it shouldn't, put items in the outer loop. Getting that backwards doesn't crash — it just quietly returns a larger, wrong number.