☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Coin Change 2 (DP - 22)

Hard TUF ID 2801 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array coins of distinct denominations and an integer amount. With an unlimited supply of every denomination, count the number of combinations of coins that add up to exactly amount. A combination is a multiset: 1 + 2 + 2 and 2 + 1 + 2 are the same combination and are counted once. If no combination works, the answer is 0.

This is LeetCode 518. Constraints: 1 ≤ coins.length ≤ 300, 1 ≤ coins[i] ≤ 5000, all values distinct, 0 ≤ amount ≤ 5000. The final answer is guaranteed to fit in a signed 32-bit integer; the Java methods return long anyway (see the pitfalls for why).

Example 1

coins = [1, 2, 5], amount = 5
answer = 4          // 5 | 2+2+1 | 2+1+1+1 | 1+1+1+1+1

Example 2

coins = [2], amount = 3
answer = 0          // sums of 2s are always even

Counting combinations without double counting

The challenge is to count 2 + 2 + 1 once rather than three times (once per ordering). The fix is to make decisions one denomination at a time: first decide how many 5s to use, then how many 2s, then how many 1s. Any combination corresponds to exactly one sequence of such decisions, because a combination is precisely “how many copies of each denomination”. So the state is (i, t): denominations coins[0..i] are still allowed, and t is the amount left.

From (i, t) there are two disjoint possibilities:

The two branches produce disjoint sets of combinations (they differ in how many copies of coin i are used), so their counts add. Base case at i = 0: only coins[0] remains, and there is exactly one way (all copies of coins[0]) if it divides t, else none. This includes t = 0, where the one way is “no coins”.

ways(0, t) = 1 if coins[0] divides t, else 0
ways(i, t) = ways(i - 1, t) + ( ways(i, t - coins[i])  if coins[i] ≤ t, else 0 )
answer     = ways(n - 1, amount)

This is the same recursion as Minimum Coins (DP - 20), with min replaced by + and “count coins” replaced by “count ways”.

Approach 1: Recursion

Intuition. Implement the recurrence directly.

Algorithm.

  1. If i == 0, return 1 if coins[0] divides t, else 0.
  2. Return ways(i - 1, t) + ways(i, t - coins[i]), the second term only when coins[i] ≤ t.
static long recursive(int[] coins, int amount) {
    return ways(coins.length - 1, amount, coins);
}

static long ways(int i, int t, int[] coins) {
    if (i == 0) return t % coins[0] == 0 ? 1 : 0;             // only coins[0] left: one way if it divides t
    long notTake = ways(i - 1, t, coins);
    long take = coins[i] <= t ? ways(i, t - coins[i], coins) : 0;   // stay on i: it may be used again
    return notTake + take;
}

Complexity. Exponential time: the depth can reach amount and every level branches twice, so O(2^amount) bounds it. Space O(amount) for the stack.

Approach 2: Memoization

Intuition. There are n · (amount + 1) states and the count from each depends only on the state. Cache them. A count of 0 is meaningful, so -1 marks “not computed”.

Algorithm.

  1. Allocate dp[n][amount + 1] filled with -1.
  2. Same recursion with lookups and stores.
static long memoization(int[] coins, int amount) {
    long[][] dp = new long[coins.length][amount + 1];
    for (long[] row : dp) Arrays.fill(row, -1);
    return memo(coins.length - 1, amount, coins, dp);
}

static long memo(int i, int t, int[] coins, long[][] dp) {
    if (i == 0) return t % coins[0] == 0 ? 1 : 0;
    if (dp[i][t] != -1) return dp[i][t];
    long notTake = memo(i - 1, t, coins, dp);
    long take = coins[i] <= t ? memo(i, t - coins[i], coins, dp) : 0;
    return dp[i][t] = notTake + take;
}

Complexity. Time O(n · amount), space O(n · amount) plus a stack up to O(amount) deep (for instance when coins[i] = 1).

Approach 3: Tabulation

Intuition. dp[i][t] reads dp[i - 1][t] (the row above) and dp[i][t - coins[i]] (the same row, to the left). Filling rows top to bottom and each row left to right guarantees both are ready. Row 0 is the base case.

Algorithm.

  1. dp[0][t] = 1 if coins[0] divides t, else 0.
  2. For i ≥ 1, t = 0..amount: dp[i][t] = dp[i - 1][t] + (coins[i] ≤ t ? dp[i][t - coins[i]] : 0).
  3. Return dp[n - 1][amount].
static long tabulation(int[] coins, int amount) {
    int n = coins.length;
    long[][] dp = new long[n][amount + 1];
    for (int t = 0; t <= amount; t++) dp[0][t] = t % coins[0] == 0 ? 1 : 0;
    for (int i = 1; i < n; i++) {
        for (int t = 0; t <= amount; t++) {
            long notTake = dp[i - 1][t];
            long take = coins[i] <= t ? dp[i][t - coins[i]] : 0;      // same row: unlimited copies of coin i
            dp[i][t] = notTake + take;
        }
    }
    return dp[n - 1][amount];
}

Complexity. Time O(n · amount), space O(n · amount).

Approach 4: Space optimized

Intuition. Keep one row ways. Before coin c is processed it holds the counts using the earlier coins only; adding ways[t - c] into ways[t] for t going upward uses a ways[t - c] that already includes coin c, which is exactly the same-row read of the tabulation. Starting from ways[0] = 1 (the empty combination) and zeros elsewhere is equivalent to the base row.

The order of the loops is the whole point. Coins outside, amounts inside counts combinations: all uses of coin c are decided in one pass, before later coins are considered, so each multiset is built in exactly one order. Swapping the loops (amounts outside, coins inside) counts ordered sequences instead: for [1, 2, 5] and amount 5 it returns 9, because 2 + 2 + 1, 2 + 1 + 2 and 1 + 2 + 2 are counted separately. That different problem is LeetCode 377, Combination Sum IV.

Algorithm.

  1. ways[0] = 1.
  2. For each coin c, for t from c to amount: ways[t] += ways[t - c].
  3. Return ways[amount].
static long spaceOptimized(int[] coins, int amount) {
    long[] ways = new long[amount + 1];
    ways[0] = 1;                                                 // one way to make 0: use no coins
    for (int c : coins) {
        for (int t = c; t <= amount; t++) ways[t] += ways[t - c];
    }
    return ways[amount];
}

Dry run on Example 1, showing ways[0..5] after each coin:

after coin ways[0..5]
start 1 0 0 0 0 0
1 1 1 1 1 1 1
2 1 1 2 2 3 3
5 1 1 2 2 3 4

After coin 2, ways[4] = 3 counts 1111, 112 and 22. Coin 5 adds one way to ways[5] (the single coin 5), giving 4.

Complexity. Time O(n · amount), space O(amount).

Edge cases and pitfalls