Search for a command to run...
What it teaches: Counting combinations: coins in the outer loop.
Practise it on judges as “Coin Change II”.
Return the number of combinations of coins (unlimited supply) that make up amount. Order doesn't matter.
Example 1
Input: amount = 5, coins = [1, 2, 5] Output: 4
Constraints
Pattern clues in the wording
These clues point to Knapsack DP: For each item, decide take or skip under a capacity; dp[c] is the best result using capacity c.
Stuck? Take one hint at a time
class Solution {
public int change(int amount, int[] coins) {
return 0;
}
}Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Test cases
| # | Input | Expected |
|---|---|---|
| 1 | amount = 5 coins = [1,2,5] | 4 |
| 2 | amount = 3 coins = [2] | 0 |
| 3 | amount = 10 coins = [10] | 1 |
From slow to fast
ways[0] = 1; for each coin, for a from coin to amount: ways[a] += ways[a − coin].
class Solution {
public 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];
}
}Verdict: The loop order is the lesson.
Before you submit
Test these inputs
Mistakes people make
Interview
How would you count combinations using each coin at most once?