Log inSign up
mediumLeetCodeNot Started

Coin Change II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

### Example 1 - Input: amount = 5, coins = [1, 2, 5] - Output: 4 - Explanation: There are four ways to make up amount 5: 1. 5 = 5 2. 5 = 2 + 2 + 1 3. 5 = 2 + 1 + 1 + 1 4. 5 = 1 + 1 + 1 + 1 + 1

### Example 2 - Input: amount = 3, coins = [2] - Output: 0 - Explanation: Amount 3 cannot be formed using only coin 2.

### Example 3 - Input: amount = 10, coins = [10] - Output: 1

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why the order of nested loops dictates combinations vs permutations in dynamic programming.
  • Formulate the unbounded counting recurrence: dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i]].
  • Reduce 2D table to 1D array of size amount + 1.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting total distinct ways / combinations.
  • Infinite supply of coins.
  • Sets with same elements in different orders are considered identical combinations.

Algorithmic Decision Tree:

  • Unbounded items + Combinations -> Outer loop = items, inner loop = amount.
  • Base case: dp[0] = 1.

Connected Patterns:

Coin ChangeCombination Sum IVPartition Equal Subset Sum

1. Include / Exclude Recursion

Intuition

For each coin index, either include the coin and keep the same index (unbounded pick), or skip to the next coin index.

Algorithm

  1. Define countWays(idx, rem).
  2. If rem == 0, return 1 (found a valid combination).
  3. If rem < 0 or idx == coins.length, return 0.
  4. Option 1 (take coin): countWays(idx, rem - coins[idx]).
  5. Option 2 (skip coin): countWays(idx + 1, rem).
  6. Return Option 1 + Option 2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int countWaysRec(int idx, int rem, const vector<int>& coins) {
7 if (rem == 0) return 1;
8 if (rem < 0 || idx == (int)coins.size()) return 0;
9
10 int take = countWaysRec(idx, rem - coins[idx], coins);
11 int skip = countWaysRec(idx + 1, rem, coins);
12 return take + skip;
13}
14
15int changeRec(int amount, vector<int>& coins) {
16 return countWaysRec(0, amount, coins);
17}
18
19int main() {
20 vector<int> coins = {1, 2, 5};
21 int amount = 5;
22 cout << "Combinations (Recursive): " << changeRec(amount, coins) << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(2^(amount / min_coin))
  • Space complexity: O(amount + coins.length) recursion stack

2. 2D Dynamic Programming Tabulation

Intuition

Construct a 2D table dp[n + 1][amount + 1] where dp[i][a] is the number of combinations using a subset of the first i coins to form amount a.

Algorithm

  1. Create dp of size (n + 1) x (amount + 1) filled with 0.
  2. For i = 0 to n: dp[i][0] = 1.
  3. For i = 1 to n:
  4. For a = 0 to amount:
  5. dp[i][a] = dp[i - 1][a]
  6. If coins[i - 1] <= a:
  7. dp[i][a] += dp[i][a - coins[i - 1]]
  8. Return dp[n][amount].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int change2D(int amount, vector<int>& coins) {
7 int n = coins.size();
8 vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
9
10 for (int i = 0; i <= n; i++) dp[i][0] = 1;
11
12 for (int i = 1; i <= n; i++) {
13 for (int a = 0; a <= amount; a++) {
14 dp[i][a] = dp[i - 1][a];
15 if (coins[i - 1] <= a) {
16 dp[i][a] += dp[i][a - coins[i - 1]];
17 }
18 }
19 }
20 return dp[n][amount];
21}
22
23int main() {
24 vector<int> coins = {1, 2, 5};
25 int amount = 5;
26 cout << "Combinations (2D DP): " << change2D(amount, coins) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n * amount)
  • Space complexity: O(n * amount)

3. Space-Optimized 1D DP Tabulation

Intuition

Maintain a single array dp of size amount + 1. Process each coin sequentially, updating dp[a] += dp[a - c] in forward order.

Algorithm

  1. Create array dp of size amount + 1 filled with 0.
  2. dp[0] = 1.
  3. For each coin c in coins:
  4. For a = c to amount:
  5. dp[a] += dp[a - c].
  6. Return dp[amount].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int changeOptimal(int amount, vector<int>& coins) {
7 vector<int> dp(amount + 1, 0);
8 dp[0] = 1;
9
10 for (int c : coins) {
11 for (int a = c; a <= amount; a++) {
12 dp[a] += dp[a - c];
13 }
14 }
15 return dp[amount];
16}
17
18int main() {
19 vector<int> coins = {1, 2, 5};
20 int amount = 5;
21 cout << "Combinations (Optimal 1D DP): " << changeOptimal(amount, coins) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(coins.length * amount)
  • Space complexity: O(amount) space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Include/Exclude DFSO(2^(amount / min_coin))O(amount + n)Recursion choosing to take coin or advance index.Recomputes same (idx, rem) states
2.2D TabulationO(n * amount)O(n * amount)dp[i][a] with explicit coin index and amount dimensions.Table allocation
3.1D TabulationOptimalO(n * amount)O(amount)Coins outer loop, amount inner forward loop.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Putting amount loop on the outside (solves Combination Sum IV permutations instead).

Pitfall 2:

Iterating backwards in inner loop (turns unbounded knapsack into 0/1 knapsack where each coin can only be used once).

Crucial Edge Cases to Validate:

  • amount = 0: Output is 1 (exactly 1 way: pick no coins).
  • No coins can form amount: Output is 0.
  • Single coin divides amount: Output is 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the fundamental distinction between Coin Change II (combinations, coins loop outside) and Combination Sum IV (permutations, amount loop outside). Interviewers frequently test this exact distinction!

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What happens if you swap the nested loops in Coin Change II (outer loop over amounts, inner loop over coins)?

Back to DSA Sheet