Coin Change Problem
Problem
Given coin denominations (unlimited supply) and an amount, return the fewest coins that make up the amount, or −1 if it cannot be made. Coin Change II asks instead for the number of distinct combinations.
Example 1
Input: coins = [1, 2, 5], amount = 11 Output: 3
5 + 5 + 1.
Example 2
Input: coins = [2], amount = 3 Output: -1
Also asked as: coin change · minimum number of coins
Test cases
Case 1
Input: [1,2,5], 11 Expected: 3
Case 2
Input: [2], 3 Expected: -1
Case 3
Input: [1], 0 Expected: 0
View solutionHide solution2 approaches
1. Bottom-up (min coins for each amount)
Time O(amount · coins)Space O(amount)
dp[a] = 1 + min over coins c≤a of dp[a−c]. Unbounded knapsack shape.
function coinChange(coins, amount) { const dp = 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] = Math.min(dp[a], dp[a - c] + 1); return dp[amount] === Infinity ? -1 : dp[amount];}2. Count the number of ways
Time O(amount · coins)Space O(amount)
Different question, same table: iterate coins in the outer loop so combinations aren’t double-counted.
function changeWays(coins, amount) { const dp = 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];}