114.Coin Change II

Medium2-D Dynamic Programming · 4/11

Problem

You are given an integer amount and an array coins of distinct denominations. You have an unlimited supply of each coin.

Return the number of combinations of coins that add up to exactly amount. Order does not matter — 1+2 and 2+1 are the same combination. If the amount cannot be made, return 0. The answer fits in a signed 32-bit integer.

Examples

Input:  amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: 5 = 5
             5 = 2 + 2 + 1
             5 = 2 + 1 + 1 + 1
             5 = 1 + 1 + 1 + 1 + 1

Input:  amount = 3, coins = [2]
Output: 0
Explanation: Only even amounts can be made with 2s.

Input:  amount = 10, coins = [10]
Output: 1

Constraints

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All values of coins are unique.
0 <= amount <= 5000

💡 Key Insight

To count combinations (not permutations), fix an order on the coins and decide coin by coin: for coin i, either use it once more (stay on coin i, amount shrinks) or move on to coin i + 1 forever. That gives ways(i, a) = ways(i, a - coins[i]) + ways(i + 1, a) — the unbounded knapsack. In table form, with the coin loop outside the amount loop, a single 1-D array dp[a] += dp[a - coin] does it.

Recursion (Brute Force)

TimeExponentialSpaceO(amount / minCoin + n)

Intuition

count(i, a) = number of ways to make amount a using only coins i, i+1, .... Because we never go back to an earlier coin, each multiset of coins is generated exactly once.

Algorithm

count(i, a):
- If a == 0, return 1 (found one combination).
- If a < 0 or i == coins.length, return 0.
- Return count(i, a - coins[i]) + count(i + 1, a).
Return count(0, amount).

Visualization

flowchart TD
    A["count(0, 3)<br/>coins [1,2]"] -->|"use 1"| B["count(0, 2)"]
    A -->|"skip 1"| C["count(1, 3)"]
    B -->|"use 1"| D["count(0, 1)"]
    B -->|"skip 1"| E["count(1, 2)"]
    D -->|"use 1"| F["count(0, 0) = 1<br/>1+1+1"]
    D -->|"skip 1"| G["count(1, 1) = 0"]
    E -->|"use 2"| H["count(1, 0) = 1<br/>1+2"]
    C -->|"use 2"| I["count(1, 1) = 0"]
    C -->|"skip 2"| J["count(2, 3) = 0"]

Total = 2 combinations (1+1+1, 1+2); 2+1 is never generated because after skipping coin 1 we can't return to it.

Code

java

class Solution {
    public int change(int amount, int[] coins) {
        return count(coins, 0, amount);
    }

    private int count(int[] coins, int i, int a) {
        if (a == 0) {
            return 1; // exact amount reached
        }
        if (a < 0 || i == coins.length) {
            return 0; // overshot or no coins left
        }
        // take coin i again, or stop using coin i
        return count(coins, i, a - coins[i]) + count(coins, i + 1, a);
    }
}

Complexity

Time: Exponential — roughly O(2^(amount / minCoin + n)) in the worst case.
Space: O(amount / minCoin + n) — recursion depth.

Top-Down Memoization

TimeO(n · amount)SpaceO(n · amount)

Intuition

The state (i, a) fully determines the answer, and there are only n · (amount + 1) of them. Cache each one.

Algorithm

memo = new Integer[n][amount + 1].
Same recursion; return the cached value when present.

Dry Run

amount = 5, coins = [1, 2, 5]

count(2, a)  coins {5}      a = 0..5 : [1, 0, 0, 0, 0, 1]
count(1, a)  coins {2,5}    a = 0..5 : [1, 0, 1, 0, 1, 1]
count(0, a)  coins {1,2,5}  a = 0..5 : [1, 1, 2, 2, 3, 4]

count(0, 5) = count(0, 4) + count(1, 5) = 3 + 1 = 4

Each count(i, a) is computed once; later calls (e.g. count(1, 2) reached from both count(1, 4) and count(0, 2)) are cache hits.

Code

java

class Solution {
    private Integer[][] memo;
    private int[] coins;

    public int change(int amount, int[] coins) {
        this.coins = coins;
        memo = new Integer[coins.length][amount + 1];
        return count(0, amount);
    }

    private int count(int i, int a) {
        if (a == 0) {
            return 1;
        }
        if (a < 0 || i == coins.length) {
            return 0;
        }
        if (memo[i][a] != null) {
            return memo[i][a];
        }
        int ways = count(i, a - coins[i]) + count(i + 1, a);
        memo[i][a] = ways;
        return ways;
    }
}

Complexity

Time: O(n · amount) — each state computed once with O(1) work.
Space: O(n · amount) — memo, plus recursion depth up to amount + n.

Bottom-Up 2-D Tabulation

TimeO(n · amount).SpaceO(n · amount).

Intuition

Let dp[i][a] = ways to make a using the first i coins. Either coin i-1 is not used at all (dp[i-1][a]), or it is used at least once — remove one copy and we are still allowed to use it (dp[i][a - coin]).

Recurrence: dp[i][a] = dp[i-1][a] + (a >= coin ? dp[i][a - coin] : 0), with dp[i][0] = 1.

Algorithm

dp = new int[n + 1][amount + 1], dp[i][0] = 1 for all i.
For i = 1..n, for a = 1..amount, apply the recurrence with coin = coins[i-1].
Return dp[n][amount].

Dry Run

amount = 5, coins = [1, 2, 5]:

coins used \ a	0	1	2	3	4	5
none	1	0	0	0	0	0
{1}	1	1	1	1	1	1
{1,2}	1	1	2	2	3	3
{1,2,5}	1	1	2	2	3	4

Example: dp[{1,2}][4] = dp[{1}][4] + dp[{1,2}][2] = 1 + 2 = 3.

Code

java

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1; // one way to make 0: use nothing
        }
        for (int i = 1; i <= n; i++) {
            int coin = coins[i - 1];
            for (int a = 1; a <= amount; a++) {
                dp[i][a] = dp[i - 1][a]; // don't use this coin
                if (a >= coin) {
                    dp[i][a] += dp[i][a - coin]; // use it (can reuse: same row)
                }
            }
        }
        return dp[n][amount];
    }
}

Complexity

Time: O(n · amount).
Space: O(n · amount).

Space-Optimized 1-D DPOptimal

TimeO(n · amount)SpaceO(amount)

Intuition

Row i reads row i - 1 at the same column and row i to the left. With one array, dp[a] still holds the previous row's value before we update it, and dp[a - coin] has already been updated to the current row. So dp[a] += dp[a - coin] iterating a upward is exactly the recurrence. Coins must be the outer loop — swapping the loops would count permutations instead.

Algorithm

dp = new int[amount + 1], dp[0] = 1.
For each coin: for a from coin to amount: dp[a] += dp[a - coin].
Return dp[amount].

Dry Run

flowchart TD
    A["start<br/>dp = [1,0,0,0,0,0]"] -->|"coin 1"| B["dp = [1,1,1,1,1,1]"]
    B -->|"coin 2: dp[a] += dp[a-2]"| C["dp = [1,1,2,2,3,3]"]
    C -->|"coin 5: dp[5] += dp[0]"| D["dp = [1,1,2,2,3,4]"]
    D --> E["answer dp[5] = 4"]

Code

java

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1; // empty combination
        for (int coin : coins) {              // coins outside → combinations
            for (int a = coin; a <= amount; a++) {
                dp[a] += dp[a - coin];        // add ways that use this coin
            }
        }
        return dp[amount];
    }
}

Complexity

Time: O(n · amount) — every coin sweeps the amounts once.
Space: O(amount) — one array.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	Exponential	O(amount + n)
Top-Down Memoization	O(n · amount)	O(n · amount)
Bottom-Up 2-D Tabulation	O(n · amount)	O(n · amount)
Space-Optimized 1-D DP	O(n · amount)	O(amount)

Common Pitfalls

Putting the amount loop outside and the coin loop inside — that counts permutations (1+2 and 2+1 separately), which is Combination Sum IV, not this problem.
Iterating a downward in the 1-D version — that turns it into 0/1 knapsack (each coin used at most once).
Forgetting dp[0] = 1 — with it at 0, everything stays 0. Note amount = 0 must return 1.
Confusing this with Coin Change (I), which asks for the minimum number of coins (min, not +).
Intermediate counts for unreachable-prefix combos can exceed int on adversarial inputs; Java int addition wraps consistently, so the final (guaranteed 32-bit) answer is still correct — but don't use -1 as a memo sentinel; use Integer null.