Coin Change II — Solution in Python, Java & C++
Coin Change II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Coin Change II is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have an infinite supply of each coin in coins.
Return the number of combinations that add up to amount. Two combinations differ only by which coins they use and how many of each — order does not matter. Return 0 if the amount cannot be made.
Example 1
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1.
Example 2
Input: amount = 3, coins = [2]
Output: 0
Example 3
Input: amount = 10, coins = [10]
Output: 1
Constraints
1 <= coins.length <= 3001 <= coins[i] <= 5000All values in coins are distinct.0 <= amount <= 5000The answer fits in a signed 32-bit integer.
Hints for Coin Change II
Hint 1
Count combinations, not permutations —
1+2and2+1are the same.Hint 2
Put the coin loop outside and the amount loop inside; that fixes an order on the coins and stops permutations being counted.
Hint 3
dp[a]is the number of ways to makeausing the coins considered so far.
How to solve Coin Change II
A one-dimensional knapsack over coin types. Processing one coin at a time and sweeping the amounts upwards counts each multiset exactly once, because a combination is built in a fixed coin order.
Approach
- Set
dp[0] = 1— one way to make nothing. - For each coin
c, sweepafromctoamountdoingdp[a] += dp[a - c]. - Return
dp[amount].
Why it works
With the coin loop outermost, dp[a] after processing coins 0…i counts the ways to make a using only those coins — and each combination is generated once, in non-decreasing coin index. Swapping the loops would let the same multiset be built in several orders, which counts permutations instead. Sweeping a upwards (rather than downwards) is what allows a coin to be reused.
Complexity
- Time —
O(n · amount) - Space —
O(amount)
Pitfalls
- Putting the amount loop outside counts permutations — the answer explodes.
- Sweeping
adownwards turns it into the 0/1 knapsack, where each coin is used at most once. dp[0] = 1is the base case; starting at 0 makes every answer 0.
Reference solution
Python
from typing import List
def change(amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins:
for a in range(c, amount + 1):
dp[a] += dp[a - c]
return dp[amount]Java
public static int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int c : coins) {
for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
}
return dp[amount];
}C++
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int c : coins) {
for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
}
return dp[amount];
}JavaScript
var change = function(amount, coins) {
var dp = [];
for (var t = 0; t <= amount; t++) dp.push(0);
dp[0] = 1;
for (var i = 0; i < coins.length; i++) {
for (var a = coins[i]; a <= amount; a++) dp[a] += dp[a - coins[i]];
}
return dp[amount];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming