☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Coin change II

Hard TUF ID 316 SDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array coins of distinct positive denominations and a non-negative integer amount. You have an unlimited number of coins of every denomination. Count how many combinations of coins add up to exactly amount. Order does not matter: 2 + 2 + 1 and 1 + 2 + 2 are the same combination.

Constraints (LeetCode 518): 1 ≤ coins.length ≤ 300, 1 ≤ coins[i] ≤ 5000, 0 ≤ amount ≤ 5000. The final answer fits in a 32-bit signed integer. The Java methods return long because intermediate table entries for smaller amounts are not covered by that guarantee.

The Blind 75 list pairs this row with the sister problem Coin Change (LeetCode 322): with the same unlimited coins, find the fewest coins that make amount. That variant is covered in its own section near the end.

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          // any number of 2s gives an even total

The key idea: decide one denomination at a time

If we counted “sequences of coins whose sum is amount”, then 2 + 1 and 1 + 2 would be counted separately, and the answer for Example 1 would be 9, not 4. To count each multiset once, we impose an order on the decisions, not on the coins in the sum: first decide how many copies of coins[0] to use, then how many of coins[1], and so on. A combination is nothing more than a count for each denomination, so every combination corresponds to exactly one such sequence of decisions.

Let count(i, rem) be the number of ways to pay rem using only coins[i..n-1]. At state (i, rem) there are two disjoint choices:

The two branches never produce the same combination, because they differ in how many copies of coins[i] they use. So their counts simply add:

count(i, 0)  = 1                        // paid in full: one finished combination
count(n, r)  = 0   for r > 0            // nothing left to pay with
count(i, r)  = count(i + 1, r) + ( count(i, r - coins[i])  if coins[i] ≤ r )
answer       = count(0, amount)

Approach 1: Recursion

Intuition. Implement the recurrence as written. The base case rem == 0 is checked first, which makes amount = 0 correctly return 1 (the empty combination).

Algorithm.

  1. If rem == 0, return 1.
  2. If i == n, return 0.
  3. Return count(i + 1, rem) plus, when coins[i] ≤ rem, count(i, rem - coins[i]).
static long recursion(int[] coins, int amount) {
    return count(0, amount, coins);
}

static long count(int i, int rem, int[] coins) {
    if (rem == 0) return 1;                                  // nothing left to pay: one finished combination
    if (i == coins.length) return 0;                         // money left but no denominations left
    long skip = count(i + 1, rem, coins);                    // never use coins[i] again
    long take = coins[i] <= rem ? count(i, rem - coins[i], coins) : 0;   // one more coins[i], stay on i
    return skip + take;
}

Complexity. Time is exponential: in the worst case (a coin of value 1) the depth reaches amount + n and every level branches twice. Space O(amount + n) for the stack.

Approach 2: Memoization

Intuition. The arguments are just (i, rem), so there are at most n × (amount + 1) distinct calls. Different decision sequences keep landing on the same state: with coins = [1, 2, 5] and amount = 5, “four 1s, then skip” and “no 1s, then two 2s” both arrive at (2, 1). Caching each state turns the exponential tree into a table fill. -1 is a safe marker because a count is never negative.

Algorithm.

  1. Allocate dp[n][amount + 1] filled with -1.
  2. Run the recursion; return the cached value when present, and store each new result.
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(0, amount, coins, dp);
}

static long memo(int i, int rem, int[] coins, long[][] dp) {
    if (rem == 0) return 1;
    if (i == coins.length) return 0;
    if (dp[i][rem] != -1) return dp[i][rem];
    long skip = memo(i + 1, rem, coins, dp);
    long take = coins[i] <= rem ? memo(i, rem - coins[i], coins, dp) : 0;
    return dp[i][rem] = skip + take;
}

Complexity. Time O(n × amount): each state does O(1) work. Space O(n × amount) for the table plus up to O(amount + n) stack. For the largest inputs the stack depth can approach 5300 frames, which is fine for Java’s default stack but is one more reason to prefer the iterative versions.

Approach 3: Tabulation

Intuition. count(i, r) reads count(i + 1, r) (the next row) and count(i, r - coins[i]) (the same row, further left). So fill rows from i = n - 1 down to 0, and within a row fill r from small to large. Row n is the base case: only r = 0 has one way.

Algorithm.

  1. dp[n][0] = 1, everything else in row n is 0.
  2. For i from n - 1 down to 0, for r from 0 to amount: dp[i][r] = dp[i + 1][r] + (coins[i] ≤ r ? dp[i][r - coins[i]] : 0).
  3. Return dp[0][amount].
static long tabulation(int[] coins, int amount) {
    int n = coins.length;
    long[][] dp = new long[n + 1][amount + 1];               // dp[i][r]: combinations for r using coins[i..n-1]
    dp[n][0] = 1;                                            // no coins: only r = 0 is reachable
    for (int i = n - 1; i >= 0; i--) {
        for (int r = 0; r <= amount; r++) {
            dp[i][r] = dp[i + 1][r];
            if (coins[i] <= r) dp[i][r] += dp[i][r - coins[i]];
        }
    }
    return dp[0][amount];
}

Complexity. Time O(n × amount). Space O(n × amount).

Approach 4: Space optimised

Intuition. Each row needs only the row below it and its own left part. With a single array, before updating ways[r] it still holds the value from the previous coin (the “skip” term), and ways[r - c] has already been updated for the current coin (the “take” term, which allows repeats). So one ascending pass per coin is exactly the recurrence.

Read this way, the code says: “after processing coins c1..ck, ways[r] is the number of combinations of those coins summing to r.” Adding coin c lets every combination for r - c be extended by one more c.

Algorithm.

  1. ways[0] = 1.
  2. For each coin c, for r from c up to amount: ways[r] += ways[r - c].
  3. Return ways[amount].
static long spaceOptimised(int[] coins, int amount) {
    long[] ways = new long[amount + 1];                      // ways[r]: combinations for r with the coins seen so far
    ways[0] = 1;
    for (int c : coins) {
        for (int r = c; r <= amount; r++) ways[r] += ways[r - c];   // ascending r lets c be reused
    }
    return ways[amount];
}

Dry run on Example 1 (coins = [1, 2, 5], amount = 5), showing ways[0..5] after each coin:

after coin r = 0 1 2 3 4 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

Complexity. Time O(n × amount). Space O(amount).

Why the loop order matters. If you swap the loops (amount outside, coins inside), each ways[r] is built from ways[r - c] for every coin, in any order, and you count permutations: Example 1 would give 9. Coins outside means coins are introduced in a fixed order, which is precisely the “one denomination at a time” argument above.

Variant: Coin Change, fewest coins (Blind 75)

The Blind 75 entry asks for the minimum number of coins to make amount, or -1 if impossible. Same unlimited supply, same state space, but we minimise instead of add. Let best[r] be the fewest coins summing to r. The last coin used is some c ≤ r, and the rest must be an optimal way to make r - c, so best[r] = 1 + min over c of best[r - c], with best[0] = 0. Here loop order does not matter, because we take a minimum rather than counting distinct arrangements.

static int fewestCoins(int[] coins, int amount) {
    int inf = Integer.MAX_VALUE;
    int[] best = new int[amount + 1];
    Arrays.fill(best, inf);
    best[0] = 0;
    for (int r = 1; r <= amount; r++) {
        for (int c : coins) {
            if (c <= r && best[r - c] != inf) best[r] = Math.min(best[r], best[r - c] + 1);
        }
    }
    return best[amount] == inf ? -1 : best[amount];
}

Time O(n × amount), space O(amount). Greedy (“always take the largest coin that fits”) is wrong here: with coins [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1 (3 coins) but 3 + 3 uses 2.

Edge cases and pitfalls