The problem. Given coin values coins (with an unlimited supply of each) and an amount, return the fewest coins that add up to exactly amount, or -1 if it can't be done.
![coins are 1, 3 and 4, amount 6. fewest[a] is the fewest coins that make a: 0, 1, 2, 1, 1, 2, 2 for a = 0 to 6. fewest[6] tries each coin as the last one: 1 + min(fewest[5], fewest[3], fewest[2]) = 1 + min(2, 1, 2) = 2, using 3 + 3. Greedy, which grabs the 4 first, needs 4 + 1 + 1: three coins.](/drawings/68d44695-640d-4567-8a7e-c3022e14378d.svg)
coins = [1, 2, 5], amount = 11 -> 3 (5 + 5 + 1)
coins = [2], amount = 3 -> -1
coins = [1], amount = 0 -> 0
coins = [1, 3, 4], amount = 6 -> 2 (3 + 3; greedy would give 4 + 1 + 1)Greedy — always grab the biggest coin that fits — works for real currency but not in general: with [1, 3, 4] and 6 it takes 4 + 1 + 1 when 3 + 3 is better. Instead, think about the last coin. If it's c, the rest is the best way to make amount - c. You don't know which c is best, so try them all: `fewest[a] = 1 + min(fewest[a - c])` over every coin c ≤ a, with fewest[0] = 0. Each coin can be used again, so this is the unbounded knapsack.
function coinChange(coins, amount) { const memo = new Map(); // left -> fewest coins const fewest = (left) => { // fewest coins that make exactly left if (left === 0) return 0; if (memo.has(left)) return memo.get(left); let best = Infinity; for (const c of coins) { if (c <= left) best = Math.min(best, fewest(left - c) + 1); // c is the last coin } memo.set(left, best); return best; }; const answer = fewest(amount); return answer === Infinity ? -1 : answer;}Time O(amount · k), space O(amount) for k coins. Without the memo it's exponential: 6 is reached as 5 + 1, 3 + 3, 2 + 4, and so on, each solved again. The recursion can go amount calls deep — with LeetCode's amount ≤ 10,000 that overflows Python's default limit of 1,000 frames, which is a good reason to build the table bottom-up.
Each amount tries every coin as the last one and keeps the fewest.
function coinChange(coins, amount) { const fewest = new Array(amount + 1).fill(Infinity); // fewest[a]: coins to make a fewest[0] = 0; for (let a = 1; a <= amount; a++) { for (const c of coins) { if (c <= a) fewest[a] = Math.min(fewest[a], fewest[a - c] + 1); // end with coin c } } return fewest[amount] === Infinity ? -1 : fewest[amount];}Time O(amount · k), space O(amount). Java and C++ use amount + 1 as infinity: even all 1-coins need only amount, and it can't overflow when 1 is added. The loop goes upwards, so fewest[a - c] may already use coin c — that's what lets a coin repeat.
Picture every amount from 0 to amount as a node, with an edge a → a + c for each coin. The fewest coins is the shortest path from 0 to amount, and BFS finds it level by level: level 1 is everything one coin makes, level 2 everything two coins make, and so on.
function coinChange(coins, amount) { if (amount === 0) return 0; const seen = new Array(amount + 1).fill(false); let level = [0]; // amounts made with used - 1 coins for (let used = 1; level.length; used++) { const next = []; for (const a of level) { for (const c of coins) { if (c > amount - a) continue; // overshoots const b = a + c; if (b === amount) return used; // the first time we reach it is the fewest if (!seen[b]) { seen[b] = true; next.push(b); } } } level = next; } return -1;}Time O(amount · k), space O(amount). The same bound as the table, but BFS stops as soon as it reaches amount, which helps when the answer is a few big coins.
[2] and 3: -1.[1, 3, 4] and 6: 2, not 3.amount: never used, and a + c mustn't overflow.