Coin Change II
The briefingthe full drill, in my own words
The drill: Given coin denominations and a target amount, count how many different combinations of coins add up to it exactly — order doesn't matter, and each denomination can be reused any number of times.
A set of coin denominations and a target amount arrive together, and the task is to count how many different combinations of those coins add up to the target exactly.
Each denomination can be used any number of times, and order doesn't matter for counting — using a 1-coin then a 2-coin is the same combination as a 2-coin then a 1-coin, so it's only counted once, not twice.
The output is that combination count, which is zero when no combination of the given coins can reach the target exactly.
- coin denominations are distinct positive values
- each denomination can be reused any number of times
- order doesn't matter, so permutations of the same coins count once
- the target and coin count stay small enough for an O(amount·coins) table
The hintstake only what you need
HINT 1 THE NUDGE
Two combinations that use the same coins in a different order aren't different combinations. Processing coins one whole denomination at a time — instead of one choice at a time — is what keeps order from being double counted.
HINT 2 THE STRUCTURE
With a fixed set of coins considered so far, the ways to make amount a either skip the newest coin entirely, or use at least one of it — using one just needs the ways to make a minus that coin's value, with the same coin still allowed again.
HINT 3 ONE STEP FROM THE ANSWER
DP over amount: ways[0] = 1. For each coin in turn, sweep amounts upward from that coin's value and do ways[a] += ways[a − coin]. Finishing one coin's whole sweep before starting the next is what prevents order from mattering.
Coach's boardthe pattern, step by step
amount=5, coins=[1,2]. ways[0]=1 — the empty combination reaches zero; everything else is unknown so far.
The splitstwo paces, two languages
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]
return dp[amount]class Solution:
def change(self, amount: int, coins: List[int]) -> int:
def count(i, remaining):
if remaining == 0:
return 1
if i == len(coins) or remaining < 0:
return 0
return count(i + 1, remaining) + count(i, remaining - coins[i])
return count(0, amount)class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int a = coin; a <= amount; a++) {
dp[a] += dp[a - coin];
}
}
return dp[amount];
}
}class Solution {
private int[] coins;
public int change(int amount, int[] coins) {
this.coins = coins;
return count(0, amount);
}
private int count(int i, int remaining) {
if (remaining == 0) {
return 1;
}
if (i == coins.length || remaining < 0) {
return 0;
}
return count(i + 1, remaining) + count(i, remaining - coins[i]);
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED