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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- 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
Given distinct coin denominations coins (infinite supply) and a total amount, return the number of combinations that make up that amount (order does not matter). If it cannot be made, return 0.
Example 1
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1.
Example 2
Input: amount = 3, coins = [2]
Output: 0
Constraints
1 <= coins.length <= 51 <= coins[i] <= 20 (distinct)0 <= amount <= 60
Hints for Coin Change II
Hint 1
Loop coins on the OUTSIDE so each combination is counted once.
Hint 2
dp[a] += dp[a - c] for each coin c.
How to solve Coin Change II
Counting combinations rather than permutations hinges entirely on loop order. Put the coins on the outer loop and the amounts on the inner one: that way each coin is considered once as a whole, so [1,2] and [2,1] are never counted as different answers.
Approach
- Create
ways[0 .. amount], all zero exceptways[0] = 1— there is exactly one way to make nothing. - For each coin
c(outer loop): - Sweep
afromcup toamountand addways[a - c]toways[a]. - Return
ways[amount].
Why it works
After processing the first k coins, ways[a] counts the combinations of a using only those coins — so no ordering is ever introduced, because a coin is only ever added to totals already built from coins earlier in the list. Sweeping the amount upwards within a coin is what permits reusing that coin any number of times: ways[a - c] may itself already include copies of c. Swapping the loops would instead count ordered sequences, the answer to a different problem.
Complexity
- Time —
O(amount · coins) - Space —
O(amount)
Pitfalls
- Coins outer, amounts inner. Reversing the loops counts permutations and inflates the answer.
ways[0] = 1is the seed that makes everything else non-zero.- Sweep the amount upwards (not downwards) — downwards would forbid reusing the coin, solving the 0/1 knapsack instead.
- An unmakeable amount naturally ends at
0; no sentinel is needed.
Reference solution
Python
from typing import List
def change(amount: int, coins: List[int]) -> int:
dp = [1] + [0] * amount
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[] ways = new int[amount + 1];
ways[0] = 1;
for (int c : coins) {
for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
}
return ways[amount];
}C++
int change(int amount, vector<int>& coins) {
vector<int> ways(amount + 1, 0);
ways[0] = 1;
for (int c : coins) {
for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
}
return ways[amount];
}JavaScript
var change = function(amount, coins) {
const dp = new 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];
};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