Coin Change
Coin Change is LeetCode 322 (Medium). You are given an array coins of distinct denominations and a target amount. You may use as many coins of each denomination as you like. Return the fewest coins whose values add up to exactly amount.
If no mix of coins reaches the amount, return -1.
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2³¹ - 1
- 0 <= amount <= 10⁴
Intuition
The tempting move is greedy: keep taking the largest coin that fits. It works for everyday currency but fails for arbitrary coin sets, because a big coin now can leave an awkward remainder.
What always works is to look at the last coin of an optimal answer. If it is c, the coins before it must make amount - c with as few coins as possible, otherwise a better set for that remainder would beat the optimum. So the best count for any amount is one more than the best count for some smaller amount, and trying every coin as the last one finds it. That is dynamic programming coin change: small amounts are solved first and reused.
Minimise the number of items that sum to a target, with each item reusable any number of times. That is the unbounded knapsack shape. The state is just the amount left, and every coin is retried at every amount. It is also a shortest path: amounts are nodes, each coin is an edge, and you want the fewest edges from 0 to amount.
Approach
Before reading on, check greedy on coins [1, 3, 4] and amount 6. Then decide what dp[a] should mean and which earlier entries it needs. Aim for O(amount × coins) time.
See why greedy is not enough
Largest-first picks 4, 1, 1 for amount 6 with coins [1, 3, 4]; the optimum is 3, 3. A choice that looks best now can leave an awkward remainder, so every option has to be compared.
Define the state
dp[a] = the minimum number of coins that sum to exactly a, for every a from 0 to amount. Storing every smaller amount, not just the target, is what lets each answer be built from earlier ones instead of being recomputed from scratch.
Set the base case and the impossible marker
dp[0] = 0: zero coins make zero.- Every other entry starts above any real answer: infinity, or
amount + 1, since no answer can use more thanamountcoins of value 1.
That marker means "not reachable yet", and it survives every min until a real count replaces it.
Fill amounts from 1 upward
For each amount a from 1 upward, and each coin c <= a, set dp[a] = min(dp[a], dp[a - c] + 1). Because a - c < a, that entry is already final when it is read. Adding 1 to the unreachable marker still loses every min, so impossible amounts stay impossible.
Return the answer or -1
If dp[amount] is still the impossible marker, return -1; otherwise return dp[amount]. To list the coins, walk back from amount, each time subtracting a coin c with dp[a - c] = dp[a] - 1.
Coin Change solution in Python | C++ | Java
dp[a] = the fewest coins that add up to exactly a. Only dp[0] is known: zero coins make zero. Every other amount is filled from smaller amounts, because the last coin you add is some c, and the rest must make a - c as cheaply as possible.dp[a] = the fewest coins that add up to exactly a. Only dp[0] is known: zero coins make zero. Every other amount is filled from smaller amounts, because the last coin you add is some c, and the rest must make a - c as cheaply as possible.dp[a] = the fewest coins that add up to exactly a. Only dp[0] is known: zero coins make zero. Every other amount is filled from smaller amounts, because the last coin you add is some c, and the rest must make a - c as cheaply as possible.dp[1] stays at infinity. This is how impossible amounts are detected: nothing ever improves them.dp[3] stays at infinity. This is how impossible amounts are detected: nothing ever improves them.dp[3] never left infinity, so no combination of these coins adds up to 3.Common pitfalls
Using greedy (largest coin first)
for c in sorted(coins, reverse=True):
count += amount // c
amount %= cfor a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)Greedy is only correct for special coin systems. With [1, 3, 4] and 6 it returns 3 instead of 2, and with [2, 5] and 6 it gets stuck at 1 left over although 2 + 2 + 2 works.
Initialising the table with 0
dp = [0] * (amount + 1)
dp = [0] + [amount + 1] * amount
With zeros, min(dp[a], ...) keeps 0 and every amount looks free. Unknown amounts need a value larger than any real answer.
Adding 1 to infinity in a fixed-size integer
vector<int> dp(amount + 1, INT_MAX); // dp[a - c] + 1 overflows
vector<int> dp(amount + 1, amount + 1);
INT_MAX + 1 wraps to a negative number, which then wins every min. amount + 1 is safely larger than any answer and cannot overflow.
Edge cases
Return 0: no coins are needed. The loop does not run and dp[0] = 0 is returned.
For example coins [2], amount 3. dp[3] never improves from the marker, so the answer is -1.
Coins bigger than the current amount are skipped by the c <= a check, so values up to 2^31 - 1 are safe.
Complexity
amount, not the size of the input.Coin change vs related problems
Same coins, different question. The question decides both the recurrence and the loop order.
| Problem | Question | Recurrence | Loop order |
|---|---|---|---|
| Coin Change (322) | fewest coins | dp[a] = min(dp[a - c] + 1) | either order works |
| Coin Change II (518) | number of combinations | dp[a] += dp[a - c] | coins outer, amounts inner |
| Combination Sum IV (377) | number of ordered sequences | dp[a] += dp[a - c] | amounts outer, coins inner |
| Greedy change | fewest coins, canonical systems only | take the largest coin that fits | no table; wrong for [1, 3, 4] |
Coin Change FAQ
What is the coin change problem?
Given coin denominations with unlimited supply and a target amount, find the minimum number of coins that add up exactly to the amount, or report that it is impossible. For coins [1, 2, 5] and amount 11 the answer is 3 (5 + 5 + 1).
What is the dynamic programming coin change solution?
- State:
dp[a]= minimum coins to make amounta. - Base case:
dp[0] = 0; all other entries start at infinity. - Recurrence:
dp[a] = min over coins c <= a of dp[a - c] + 1. - Order: fill
a = 1, 2, ..., amount. - Answer:
dp[amount], or -1 if it is still infinity. - Complexity: O(amount × n) time, O(amount) space.
- Example: coins
[1, 2, 5], amount 11 gives 3.
Why does greedy fail for coin change?
Taking the largest coin first can leave a remainder that needs many small coins. With [1, 3, 4] and 6, greedy gives 4 + 1 + 1 = 3 coins, but 3 + 3 = 2. Greedy is only guaranteed for canonical systems such as [1, 5, 10, 25].
What is the coin change recursive solution?
f(a) = 0 if a == 0, infinity if a < 0, otherwise 1 + min(f(a - c)) over all coins. Without memoisation it is exponential; caching f(a) gives the same O(amount × n) as the table.
What is the difference between Coin Change and Coin Change II?
Coin Change asks for the fewest coins (a min recurrence). Coin Change II asks for the number of combinations that make the amount (a += recurrence), and there the loop order matters: coins in the outer loop counts each combination once.