You have an unlimited supply of each denomination in coins (an array of distinct positive integers), and you want to make up exactly amount using as few coins as possible.
Given coins and amount, return the fewest coins needed to total exactly amount. If no combination of the given coins sums to amount exactly, return -1.
Example
11 = 5 + 5 + 1, three coins — no combination of these coins does better.
Constraints
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
- coins contains no duplicate values
Intuition
A first pass just recurses on the definition: the fewest coins to make remaining is 1 plus the fewest coins to make remaining - coin, for whichever coin does best — recomputed from scratch every time the same remaining amount comes up again.
function coinChange(coins, amount) {
// Recursively find the fewest coins to make `remaining`, trying every coin as the last one placed.
function solve(remaining) {
// Nothing left to make — zero more coins needed.
if (remaining === 0) return 0;
// Overshot with the last coin tried — this path can't work.
if (remaining < 0) return Infinity;
let best = Infinity;
// Try every coin as the last coin placed, then recurse on what's left.
for (const coin of coins) {
const withCoin = 1 + solve(remaining - coin);
if (withCoin < best) best = withCoin;
}
return best;
}
const fewest = solve(amount);
// Infinity means no path of coins ever landed on exactly 0.
return fewest === Infinity ? -1 : fewest;
}This is O(coins.length^amount) — every remaining amount branches into coins.length more calls, and the same remaining amount gets solved over and over from different coin-choice paths (a 3 then a 4 leaves the same remainder as a 4 then a 3, but the recursion re-derives it independently both times). Can we do better?
The key observation: solve(remaining) depends only on remaining, not on which coins got us there — once it's been solved, its answer never changes, so it's only worth solving once. That's the overlapping-subproblems signature dynamic programming exists for.
It's tempting to reach for a greedy shortcut instead — always take the largest coin that still fits. That happens to work for coins = [1, 2, 5], but it isn't reliable in general: with coins = [1, 4, 5] and amount = 8, greedy grabs a 5 first, then has to fill the remaining 3 with three 1s — 4 coins total. DP considers every coin choice at every amount and never commits early, so it finds the 2-coin answer, 4 + 4, that greedy walked right past.
The stored solution takes the bottom-up route: fill dp[total] — the fewest coins for that total — for every total from 1 up to amount, trying each coin as the last one placed and keeping whichever leaves the cheapest remainder. A total that no coin combination reaches stays at a sentinel of Infinity; if dp[amount] never improves past it, the answer is -1.
Walking it through:
dp[total] = fewest coins to make that total, for coins = [2, 3], amount = 7
Base case: zero coins are needed to make a total of 0.
Neither coin is small enough to use here, so dp[1] is never relaxed. If the target amount itself ended on a cell like this, the final answer would be -1.
Coin 3 alone reaches total 3 in a single coin — coin 2 can't beat that from an unreached dp[1].
Both coins are tried at every total; whichever leaves the cheaper remainder wins — here coin 3 beats coin 2.
Both options tie at 3 coins (e.g. 2 + 2 + 3) — the fewest coins that make exactly 7.
Optimization
Bottom-up 1-D DP
Let dp[t] be the fewest coins that make total t, with dp[0] = 0. For every t from 1 to amount, try each coin c <= t and take the best of 1 + dp[t - c] — one of the current coin plus the best way to make the remainder. Totals that stay unreachable keep a sentinel of Infinity; if dp[amount] never got filled in, no combination works.
O(amount * coins.length) time, O(amount) space.
function coinChange(coins, amount) {
// dp[total] = fewest coins to make that total; Infinity means unreached so far.
const dp = new Array(amount + 1).fill(Infinity);
// Base case: zero coins are needed to make a total of 0.
dp[0] = 0;
// Fill every total from 1 up to amount, smallest first, so each dp[total - coin] is already final.
for (let total = 1; total <= amount; total++) {
// Try every coin as the last coin placed to reach this total.
for (const coin of coins) {
// Only usable if it fits, and only worth taking if it beats the current best for this total.
if (coin <= total && dp[total - coin] + 1 < dp[total]) {
dp[total] = dp[total - coin] + 1;
}
}
}
// If dp[amount] never improved past Infinity, no combination of coins sums to it exactly.
return dp[amount] === Infinity ? -1 : dp[amount];
}Complexity analysis
Time complexity: O(amount × coins.length). Here's why:
- The outer loop runs once for every total from 1 up to
amount—amountiterations. - The inner loop tries every coin at each total —
coins.lengthwork per iteration, each a constant-time comparison and update.
So every (total, coin) pair is relaxed exactly once, for O(amount × coins.length) overall — down from the brute force's exponential blowup, since each total is now computed once instead of re-derived on every path that reaches it.
Space complexity: O(amount). Here's why:
- The
dparray holds one entry per total from 0 toamount— O(amount) size. - There's no recursion, so no call stack to add on top.
The coins array itself adds O(coins.length), but that's dwarfed by amount in the worst case, so it isn't counted separately.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| coins = [3,7], amount = 0 | 0 | Zero amount needs zero coins, regardless of which coins are on hand. |
| coins = [6], amount = 6 | 1 | Single coin, exactly the amount — one coin does it. |
| coins = [5], amount = 3 | -1 | The only coin is bigger than the amount itself — no combination can ever reach it. |
| coins = [3], amount = 12 | 4 | One coin repeated evenly — the answer is just amount / coin, four uses of the same coin. |
| coins = [1,5], amount = 13 | 5 | Exercises reusing the same coin multiple times (unbounded supply) alongside a second denomination: 5 + 5 + 1 + 1 + 1. |
Try it yourself
Write your solution against the real judge before checking the reference.