AlgoMaster Logo

Coin Change II

mediumFrequency8 min readUpdated June 23, 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).

Example Walkthrough

Tracing amount = 5, coins = [1, 2, 5]. The memo fills from the last coin index back to the first, in the order the recursion resolves. Cells stay at -1 until their state is computed; column 0 never fills because the base case remaining == 0 returns before the memo is touched.

1Initialize: -1 means not yet computed
0
1
2
3
4
5
0
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
1/6

Code

Memoization spends O(n * amount) space on the table plus recursion overhead. The next approach fills the answers iteratively in a fixed order, which cuts the space to a single 1D array.

Approach 3: Bottom-Up DP (Space Optimized)

Intuition

Replace the top-down recursion with bottom-up iteration. Define dp[j] as the number of combinations that make up amount j. 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].

Example Walkthrough

Tracing amount = 5, coins = [1, 2, 5]. Each coin pass adds its contribution on top of the counts left by the previous coins:

1Initialize: dp[0]=1 (one way to make amount 0: use no coins)
0
1
base case
1
0
2
0
3
0
4
0
5
0
1/7

Code