AlgoMaster Logo

Coin Change II

mediumFrequencyUpdated September 3, 2026

Understanding the Problem

We need to count the number of distinct combinations (not permutations) of coins that add up to a target amount. Using coins [1, 2] to make amount 3, the combination 1+2 is the same as 2+1. We count it once.

This distinction between combinations and permutations drives the entire solution. If we were counting permutations (where order matters), a 1D DP that iterates over amounts and tries every coin at each amount would work. Since order does not matter, we need a way to avoid counting the same set of coins in different orders.

Processing coins one at a time avoids the duplicates: decide how many copies of the current coin to use, then move on and never return to it. A combination is then built in one fixed order (all 1s first, then all 2s, and so on), so "1+2" can be generated but "2+1" cannot.

Key Constraints:

  • 1 <= coins.length <= 300 --> Up to 300 different coin denominations. This is one dimension of our DP.
  • 0 <= amount <= 5000 --> The target amount goes up to 5000. This is the other dimension.
  • 1 <= coins[i] <= 5000 --> Individual coin values can be as large as the amount itself.

With coins.length up to 300 and amount up to 5000, a DP over 300 * 5000 = 1,500,000 states is fast. Brute-force recursion without memoization explores an exponential number of paths, so some form of DP is required.

Approach 1: Recursion (Brute Force)

Intuition

Count the combinations recursively, processing coins in order so that duplicates like 1+2 and 2+1 are never both generated. At coin index i, decide how many copies of coin i to use, then move to coin i+1 with whatever amount remains.

Define count(i, remaining) as the number of ways to make remaining using coins from index i onward. At each step:

  • If remaining == 0, we found one valid combination. Return 1.
  • If remaining < 0 or i == coins.length, there is no valid combination. Return 0.
  • Otherwise, try two choices: skip coin i entirely (move to i+1), or use coin i once (subtract its value, stay at index i since we can reuse it).

The sum of these two choices gives the total combinations.

Algorithm

  1. Define a recursive function count(i, remaining) where i is the current coin index and remaining is the amount left to fill.
  2. Base case: if remaining == 0, return 1 (found a valid combination).
  3. Base case: if remaining < 0 or i >= coins.length, return 0 (invalid path).
  4. Recursive case: return count(i + 1, remaining) + count(i, remaining - coins[i]).
  5. Call count(0, amount).

Example Walkthrough

Trace amount = 5, coins = [1, 2, 5]. Each call splits into "skip this coin" and "use it once":

Code

The recursion recomputes the same (coin index, remaining) pairs many times. Caching each result the first time it is computed removes the repeated work.

Approach 2: Top-Down DP (Memoization)

Intuition

The state of each subproblem is fully described by two values: the current coin index i and the remaining amount. There are at most n * (amount + 1) unique states, where n is the number of coins, so caching each result the first time it is computed bounds the total work by the number of states. Every later call with the same state returns the cached value immediately, and the exponential tree collapses to polynomial time.

We keep the recursive logic from Approach 1 and add a 2D memo table: before computing a state, check the table; after computing, store the result.

Algorithm

  1. Create a memo table of size coins.length x (amount + 1), initialized to -1 (meaning "not computed yet").
  2. Define count(i, remaining) with the same logic as Approach 1.
  3. Before the recursive calls, check memo[i][remaining]. If it is not -1, return the cached value.
  4. After computing the result, store it in memo[i][remaining].
  5. Call count(0, amount).

Visualization and Code

Loading animation...

Memoization still pays for the recursion: every state costs a function call, and the call stack grows with the amount. The next approach fills the same table of states in a fixed order with plain loops, so no call ever waits on another.

Approach 3: Bottom-Up DP (2D Table)

Intuition

Memoization touches the same n * (amount + 1) states a table would, but it reaches them through recursion and only in the order the calls happen to unwind. Tabulation computes the states in a fixed order instead. Define dp[i][j] as the number of combinations that make amount j using only the first i coins. Row 0 uses no coins, so dp[0][0] = 1 (the empty combination) and every other entry in row 0 is 0.

Each cell combines the same two choices as the recursion. The combinations that skip coin i are exactly dp[i - 1][j]. The combinations that use coin i at least once are dp[i][j - coin]: take any combination of the first i coins that makes j - coin and add one more of this coin. Reading from row i rather than row i - 1 is what lets a coin repeat, because that entry may already contain the coin. The answer is dp[n][amount].

Row i depends only on row i - 1 and on entries to its left in row i, so filling rows top to bottom and each row left to right guarantees every value is ready when it is read.

Algorithm

  1. Let n = coins.length. Create a table dp of size (n + 1) x (amount + 1), initialized to 0.
  2. Set dp[i][0] = 1 for every row i: there is one way to make amount 0, which is to use no coins.
  3. For each coin index i from 1 to n, with coin = coins[i - 1]:
    • For each amount j from 1 to amount:
      • Start with the skip count: dp[i][j] = dp[i - 1][j].
      • If j >= coin, add the use count: dp[i][j] += dp[i][j - coin].
  4. Return dp[n][amount].

Visualization and Code

Loading animation...

Once row i is complete, row i - 1 is never read again, so keeping the whole table around is wasteful. The next approach keeps a single row and updates it in place.

Approach 4: Bottom-Up DP (Space Optimized)

Intuition

The 2D table keeps every row, but row i only ever reads row i - 1 (the skip term) and row i itself (the use term). Once a row is finished, the rows above it are dead weight. Define dp[j] as the number of combinations that make up amount j using the coins processed so far, and update that single row in place, one coin at a time. The iteration order is what restricts the count to combinations: coins in the outer loop, amounts in the inner loop.

When we process coin c and update dp[j], the added term dp[j - c] counts the combinations that use coin c at least once to reach j. At that moment, dp[j - c] contains every combination built from the coins processed so far, including c itself, because j moves forward from c. Processing one coin at a time means [1, 2] and [2, 1] are never counted separately.

Swapping the loops (amounts outer, coins inner) would let every amount consider every coin at each step, which counts permutations instead of combinations. That solves a different problem (LeetCode #377, Combination Sum IV).

Algorithm

  1. Create a 1D array dp of size amount + 1, initialized to 0.
  2. Set dp[0] = 1 (there is one way to make amount 0: use no coins).
  3. For each coin c in coins:
    • For each amount j from c to amount:
      • Add dp[j - c] to dp[j].
  4. Return dp[amount].

Visualization and Code

Loading animation...