Coin Change II
Coin Change II is a medium dynamic programming problem solved with the knapsack pattern.
The best approach, optimal (1d dp, coins outer), runs in O(amount · k) time and O(amount) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from recursion over coins up.
Problem
Given coin values and an amount, return the number of combinations of coins that add up to the amount. Each coin can be used any number of times, and order does not matter.
Examples
Example 1
- Input
amount = 5, coins = [1, 2, 5]- Output
4- Why
- 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 <= 300;0 <= amount <= 5000.- Count combinations, not orderings: 1+2 and 2+1 are the same.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Recursion over coins | exponential | O(amount) |
| Optimal (1D DP, coins outer) | O(amount · k) | O(amount) |
1Recursion over coins
exponentialO(amount)At coin i, either use it again (stay at i) or move on to coin i + 1. Moving forward only is what prevents counting permutations.
- f(i, a): a == 0 → 1; i == n or a < 0 → 0.
- f(i, a - coins[i]) + f(i + 1, a).
class Solution {
public int change(int amount, int[] coins) {
return f(coins, 0, amount);
}
private int f(int[] coins, int i, int a) {
if (a == 0) return 1;
if (i == coins.length || a < 0) return 0;
return f(coins, i, a - coins[i]) + f(coins, i + 1, a);
}
}class Solution:
def change(self, amount: int, coins: List[int]) -> int:
return self.f(coins, 0, amount)
def f(self, coins: List[int], i: int, a: int) -> int:
if a == 0:
return 1
if i == len(coins) or a < 0:
return 0
return self.f(coins, i, a - coins[i]) + self.f(coins, i + 1, a)class Solution {
public:
int change(int amount, vector<int>& coins) {
return f(coins, 0, amount);
}
private:
int f(vector<int>& coins, int i, int a) {
if (a == 0) return 1;
if (i == (int) coins.size() || a < 0) return 0;
return f(coins, i, a - coins[i]) + f(coins, i + 1, a);
}
};function change(amount, coins) {
return f(coins, 0, amount);
}
function f(coins, i, a) {
if (a === 0) return 1;
if (i === coins.length || a < 0) return 0;
return f(coins, i, a - coins[i]) + f(coins, i + 1, a);
}2Optimal (1D DP, coins outer)
O(amount · k)O(amount)dp[a] = number of combinations making a using the coins processed so far. Adding coin c: dp[a] += dp[a - c] for a from c upward.
- dp[0] = 1.
- For each coin c, for a in c..amount: dp[a] += dp[a - c].
class Solution {
public 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];
}
}class Solution:
def change(self, 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]class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<unsigned long long> dp(amount + 1, 0);
dp[0] = 1;
for (int c : coins)
for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
return (int) dp[amount];
}
};function change(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];
}Edge cases to test
- amount = 0 (one way: use nothing)
Hints
Hint 1
Put the coin loop outside the amount loop. That counts each combination once, in coin order, instead of every permutation.
FAQ
What is the best time complexity for Coin Change II?
Optimal (1D DP, coins outer) runs in O(amount · k) time and O(amount) extra space.
Which pattern does Coin Change II use?
It is a dynamic programming problem that uses the knapsack pattern. Other problems with the same pattern: 0 - 1 Knapsack Problem, Fractional Knapsack, Knapsack with Duplicate Items.
Is there a brute force solution for Coin Change II?
Yes. Recursion over coins takes exponential time and O(amount) space. At coin i, either use it again (stay at i) or move on to coin i + 1.
Which edge cases should I test for Coin Change II?
amount = 0 (one way: use nothing).