#518 Coin Change II
the problem
In plain words
Return the number of combinations of coins (unlimited supply) that make up the amount. Order doesn't matter: 1+2 and 2+1 are the same combination. Return 0 if none.
in amount = 5, coins = [1,2,5]
out 4
5, 2+2+1, 2+1+1+1, 1+1+1+1+1.
in amount = 3, coins = [2]
out 0
in amount = 10, coins = [10]
out 1
- 1 ≤ coins.length ≤ 300
- 1 ≤ coins[i] ≤ 5000, all distinct
- 0 ≤ amount ≤ 5000
- The answer fits in a signed 32-bit int
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternUnbounded knapsack
To count each combination once, decide coin types in a fixed order: "use coin i (again)" or "never use coin i again".
solutions
From brute force to optimal
ways(i, rem) = ways(i, rem − coins[i]) + ways(i + 1, rem).
- rem = 0 → 1 way.
- Out of coin types → 0.
- Stay on i (reuse) or move to i + 1.
Every coin can branch at every remaining amount; no state is reused.
Recursion depth: moves to i+1 plus subtractions of the smallest coin m.
class Solution { public int change(int amount, int[] coins) { return ways(coins, 0, amount); } /** Ways to make rem using coins[i..]. Choosing "use coin i" or "move past coin i" keeps combinations unique. */ private int ways(int[] coins, int i, int rem) { if (rem == 0) return 1; if (i == coins.length) return 0; int use = coins[i] <= rem ? ways(coins, i, rem - coins[i]) : 0; // stay on i: may use it again int skip = ways(coins, i + 1, rem); // never use coin i again return use + skip; }}Only n × (A + 1) different (i, rem) pairs exist — cache them.
- Integer[][] memo, null = unknown (0 is a real answer).
Each state is computed once with O(1) work.
The memo table.
class Solution { public int change(int amount, int[] coins) { Integer[][] memo = new Integer[coins.length][amount + 1]; // null = not computed return ways(coins, 0, amount, memo); } private int ways(int[] coins, int i, int rem, Integer[][] memo) { if (rem == 0) return 1; if (i == coins.length) return 0; if (memo[i][rem] != null) return memo[i][rem]; int use = coins[i] <= rem ? ways(coins, i, rem - coins[i], memo) : 0; int skip = ways(coins, i + 1, rem, memo); return memo[i][rem] = use + skip; }}dp[i][a] = ways using the first i coin types.
- dp[i][0] = 1.
- dp[i][a] = dp[i−1][a] + dp[i][a − coin] (same row → reuse allowed).
One O(1) step per cell.
The table.
class Solution { public int change(int amount, int[] coins) { int n = coins.length; int[][] dp = new int[n + 1][amount + 1]; // dp[i][a] = ways using the first i coin types for (int i = 0; i <= n; i++) dp[i][0] = 1; // one way to make 0: take nothing for (int i = 1; i <= n; i++) { for (int a = 1; a <= amount; a++) { dp[i][a] = dp[i - 1][a]; // without coin i if (coins[i - 1] <= a) dp[i][a] += dp[i][a - coins[i - 1]]; // same row: reuse allowed } } return dp[n][amount]; }}Rows only read themselves and the row above → one array, amount loop upward.
- dp[0] = 1.
- for coin: for a = coin..A: dp[a] += dp[a − coin].
Same number of updates.
A single row.
class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { // coins OUTSIDE → each combination counted once for (int a = coin; a <= amount; a++) { // upward → a coin may be reused dp[a] += dp[a - coin]; } } return dp[amount]; }}in the room
How to say it in the interview
talk track
- Explain why the coin loop is outside: each combination is built in coin order, so it's counted exactly once.
traps
- Swapping the loops counts orderings (1+2 ≠ 2+1) — that's Combination Sum IV (LC 377), the next problem.
- dp[0] = 1, not 0: there is exactly one way to make 0 (take nothing).
what they ask next
Follow-ups
Combination Sum IV (LC 377) — order matters?
Put the amount loop outside and the coin loop inside. It's the next problem.
before you submit
Edge cases to test
- amount = 0 → 1 (the empty combination).
- No coin fits: amount 4, coins [5,10] → 0.
- [2,3], amount 7 → 1: 2+2+3 is counted once, not three times.
practise next
Similar problems
- #322Coin ChangeMediumin Dynamic Programming
- #377Combination Sum IVMediumin Dynamic Programming
- #39Combination SumMediumin Backtracking