Coin Change 2
Description
You are given an integer array coins where each element represents a coin of a specific denomination, and an integer amount representing a total amount of money.
Return the number of distinct combinations of coins that sum up to exactly amount. If no combination can produce the desired amount, return 0.
You have an infinite supply of each coin denomination. Two combinations are considered different only if they differ in the count of at least one denomination used — the order of coins does not matter. For example, using coins [1, 2], the combination {1, 1, 2} and {2, 1, 1} count as the same combination.
Examples
Example 1
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: There are four ways to make amount 5:
- 5 = 5 (one coin of denomination 5)
- 5 = 2 + 2 + 1 (two coins of 2 and one coin of 1)
- 5 = 2 + 1 + 1 + 1 (one coin of 2 and three coins of 1)
- 5 = 1 + 1 + 1 + 1 + 1 (five coins of 1)
Note that {1, 2, 2} and {2, 1, 2} are considered the same combination since order does not matter.
Example 2
Input: amount = 3, coins = [2]
Output: 0
Explanation: We only have coins of denomination 2. Using any number of 2's, we can make 0, 2, 4, 6, ... — all even numbers. Since 3 is odd, there is no way to form amount 3 using only coins of value 2.
Example 3
Input: amount = 10, coins = [10]
Output: 1
Explanation: There is exactly one way to make amount 10 using a coin of denomination 10: use one such coin. No other combination is possible since we only have one type of coin.
Constraints
- 1 ≤ coins.length ≤ 300
- 1 ≤ coins[i] ≤ 5000
- All values of coins are unique
- 0 ≤ amount ≤ 5000
Editorial
Brute Force
Intuition
The most straightforward approach is to consider each coin denomination one at a time and explore all possibilities using recursion. For each coin, we have two choices: use this coin at least once more (staying on the same coin index since we have infinite supply), or move on to the next coin denomination.
This is fundamentally an unbounded knapsack pattern — unlike the 0/1 knapsack where each item can be used only once, here each coin can be reused any number of times.
The key to avoiding duplicate combinations (like counting {1,2} and {2,1} separately) is to process coins in order. When we decide to skip coin i, we never go back to it. This ensures each combination is counted exactly once.
Think of it like shopping at a store where items are arranged on shelves from left to right. You walk along the shelves in one direction. At each shelf, you decide how many of that item to take (0 or more), then move to the next shelf. You never walk backwards.
Step-by-Step Explanation
Let's trace with amount = 5, coins = [1, 2, 5].
We call solve(coinIndex=0, remaining=5):
Step 1: At coin index 0 (coin=1), remaining=5. Two choices:
- Use coin 1: solve(0, 5-1) = solve(0, 4)
- Skip to next coin: solve(1, 5)
Step 2: Following solve(0, 4): use coin 1 again → solve(0, 3). This keeps going: solve(0, 3) → solve(0, 2) → solve(0, 1) → solve(0, 0). When remaining = 0, we found a valid combination: {1,1,1,1,1}. Return 1.
Step 3: Back at solve(0, 1), the skip branch goes to solve(1, 1). Coin 2 > remaining 1, so we skip to solve(2, 1). Coin 5 > 1, skip to solve(3, 1). Index out of bounds, return 0. So using four 1's and then trying larger coins doesn't work for the leftover 1.
Step 4: Backtrack further. At solve(0, 2), skip branch → solve(1, 2). Use coin 2: solve(1, 0) = 1. Skip: solve(2, 2). Coin 5 > 2, skip → out of bounds, return 0. So solve(1, 2) = 1 + 0 = 1. This corresponds to combination {1,1,1,2}.
Step 5: Continuing to unwind, at solve(0, 3) skip → solve(1, 3). Use coin 2: solve(1, 1) → use 2 again: remaining < 0, return 0. Skip: solve(2, 1) → 0. So solve(1, 1) = 0. Skip coin 2: solve(2, 3) → 0. solve(1, 3) = 0. This means no combination starting with two 1's uses coin 2 or 5 to fill remaining 3 (besides what we already counted).
Step 6: At the top-level skip branch solve(1, 5): use coin 2 → solve(1, 3). Use 2 again → solve(1, 1) = 0. Skip → solve(2, 1) = 0. So solve(1, 3) = 0. Skip coin 2 → solve(2, 5). Use coin 5 → solve(2, 0) = 1. Skip → solve(3, 5) = 0. So solve(2, 5) = 1. This gives combination {5}.
Step 7: solve(1, 5) also includes: use coin 2 twice → solve(1, 1) which gives 0. Use coin 2 → solve(1, 3) = 0 + 0 = 0. Hmm wait — let me retrace more carefully. solve(1, 5): use coin 2 → solve(1, 3), skip → solve(2, 5). solve(1, 3): use 2 → solve(1, 1), skip → solve(2, 3). solve(1, 1): use 2 → remaining -1 < 0, return 0. Skip → solve(2, 1) = 0. So solve(1,1)=0. solve(2,3): use 5 → remaining -2 < 0. Skip → out of bounds. = 0. So solve(1,3) = 0+0 = 0. solve(2,5): use 5 → solve(2,0) = 1. Skip → 0. = 1. So solve(1,5) = 0 + 1 = 1.
The full answer combines all recursive paths. Total = 4 combinations: {1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}.
The recursion tree is deep and branches many times, making it exponential.
Brute Force Recursion — Unbounded Coin Combinations — Watch how the recursion explores using each coin multiple times (staying at the same index) or skipping to the next denomination. Each leaf with remaining=0 is one valid combination.
Algorithm
- Define a recursive function solve(coinIndex, remaining):
- Base case: if remaining == 0, return 1 (valid combination found)
- Base case: if remaining < 0 or coinIndex == n, return 0
- Use current coin: solve(coinIndex, remaining - coins[coinIndex])
- Skip current coin: solve(coinIndex + 1, remaining)
- Return use + skip
- Return solve(0, amount)
Code
#include <vector>
using namespace std;
class Solution {
public:
int solve(vector<int>& coins, int coinIndex, int remaining) {
if (remaining == 0) return 1;
if (remaining < 0 || coinIndex == coins.size()) return 0;
// Use current coin (stay at same index) or skip to next coin
int use = solve(coins, coinIndex, remaining - coins[coinIndex]);
int skip = solve(coins, coinIndex + 1, remaining);
return use + skip;
}
int change(int amount, vector<int>& coins) {
return solve(coins, 0, amount);
}
};class Solution:
def change(self, amount: int, coins: list[int]) -> int:
def solve(coin_index, remaining):
if remaining == 0:
return 1
if remaining < 0 or coin_index == len(coins):
return 0
# Use current coin (stay at same index) or skip to next
use = solve(coin_index, remaining - coins[coin_index])
skip = solve(coin_index + 1, remaining)
return use + skip
return solve(0, amount)class Solution {
private int solve(int[] coins, int coinIndex, int remaining) {
if (remaining == 0) return 1;
if (remaining < 0 || coinIndex == coins.length) return 0;
int use = solve(coins, coinIndex, remaining - coins[coinIndex]);
int skip = solve(coins, coinIndex + 1, remaining);
return use + skip;
}
public int change(int amount, int[] coins) {
return solve(coins, 0, amount);
}
}Complexity Analysis
Time Complexity: O(amount^n) in the worst case, where n is the number of coin denominations.
For each coin, we can use it up to amount/coins[i] times. In the worst case (coin = 1), we can use it amount times. The recursion tree can have a branching factor proportional to amount at each level, leading to exponential growth. A loose upper bound is O(2^amount) for small coins.
Space Complexity: O(amount)
The recursion stack depth is bounded by the maximum number of coins used in any single combination, which is at most amount (when using coin = 1). Each stack frame uses O(1) space.
Why This Approach Is Not Efficient
The brute force has exponential time complexity. With amount up to 5000 and coins as small as 1, the recursion tree can have enormous depth and breadth.
The core inefficiency is overlapping subproblems. The call solve(coinIndex, remaining) with the same parameters is reached via many different paths. For instance, solve(1, 3) might be called when we used coin 0 twice (remaining went from 5 to 3) or when we used coin 0 zero times and coin 1 once (remaining from 5 to 3 via a different route). Each duplicate call spawns its own redundant subtree.
Since the state is fully determined by just two parameters — which coin we are considering and how much amount remains — we can cache these results. The total number of unique states is n × (amount + 1), which is at most 300 × 5001 = 1,500,300. This is perfectly manageable.
Better Approach - Memoization (Top-Down DP)
Intuition
We use the exact same recursive logic as brute force but add a 2D cache dp[coinIndex][remaining]. Before computing any recursive call, we check if the result is already stored. If it is, we return it immediately. If not, we compute it, store it, and then return.
This transforms the exponential recursion into a polynomial one. Each unique (coinIndex, remaining) pair is computed at most once. Since coinIndex ranges from 0 to n-1 and remaining ranges from 0 to amount, there are at most n × (amount + 1) unique subproblems.
The intuition remains the same as brute force — for each coin, decide to use it or skip it — but now we never redo work we have already done.
Step-by-Step Explanation
Let's trace with amount = 5, coins = [1, 2, 5]. We use memo dp[coinIndex][remaining].
Step 1: solve(0, 5). Not in memo. Use coin 1 → solve(0, 4). Not in memo.
Step 2: solve(0, 4). Use coin 1 → solve(0, 3) → ... → solve(0, 0) = 1 (base case). Skip path: solve(1, 0) = 1... wait. Let me trace more carefully.
The recursion proceeds depth-first. solve(0,5) → use coin 1 → solve(0,4) → use coin 1 → solve(0,3) → use coin 1 → solve(0,2) → use coin 1 → solve(0,1) → use coin 1 → solve(0,0) = 1.
Step 3: Back at solve(0,1): skip branch → solve(1, 1). Use coin 2: remaining becomes -1, return 0. Skip: solve(2, 1). Use coin 5: remaining -4 < 0, return 0. Skip: solve(3, 1) = 0. So solve(2, 1) = 0. solve(1, 1) = 0 + 0 = 0. Store dp[1][1] = 0.
Step 4: solve(0, 1) = 1 + 0 = 1. Store dp[0][1] = 1.
Step 5: Back at solve(0, 2): skip → solve(1, 2). Use coin 2 → solve(1, 0) = 1. Skip → solve(2, 2). Use coin 5 → -3 < 0. Skip → solve(3, 2) = 0. solve(2, 2) = 0. solve(1, 2) = 1 + 0 = 1. Store dp[1][2] = 1.
Step 6: solve(0, 2) = dp[0][1] + dp[1][2] = 1 + 1 = 2. Store dp[0][2] = 2. (Combinations: {1,1} and {2})
Step 7: solve(0, 3): skip → solve(1, 3). Use coin 2 → solve(1, 1) = dp[1][1] = 0 (MEMO HIT!). Skip → solve(2, 3) = 0. solve(1, 3) = 0. dp[1][3] = 0.
Step 8: solve(0, 3) = dp[0][2] + dp[1][3] = 2 + 0 = 2. Store dp[0][3] = 2. (Combinations: {1,1,1} and {1,2})
Step 9: solve(0, 4): skip → solve(1, 4). Use coin 2 → solve(1, 2) = dp[1][2] = 1 (MEMO HIT!). Skip → solve(2, 4) = 0. solve(1, 4) = 1. dp[1][4] = 1.
Step 10: solve(0, 4) = dp[0][3] + dp[1][4] = 2 + 1 = 3. Store dp[0][4] = 3. (Combinations: {1,1,1,1}, {1,1,2}, {2,2})
Step 11: solve(0, 5): skip → solve(1, 5). Use coin 2 → solve(1, 3) = dp[1][3] = 0 (HIT). Skip → solve(2, 5). Use coin 5 → solve(2, 0) = 1. Skip → solve(3, 5) = 0. solve(2, 5) = 1. dp[2][5] = 1. solve(1, 5) = 0 + 1 = 1. dp[1][5] = 1.
Step 12: solve(0, 5) = dp[0][4] + dp[1][5] = 3 + 1 = 4. Answer = 4.
Memoization — Caching Coin Change Subproblems — Watch how memoization stores computed results and returns them instantly when the same (coinIndex, remaining) pair is encountered again, converting exponential recursion to polynomial.
Algorithm
- Create a 2D memo table dp[n][amount+1] initialized to -1
- Define solve(coinIndex, remaining):
- If remaining == 0, return 1
- If remaining < 0 or coinIndex == n, return 0
- If dp[coinIndex][remaining] ≠ -1, return it (cache hit)
- Compute result = solve(coinIndex, remaining - coins[coinIndex]) + solve(coinIndex + 1, remaining)
- Store dp[coinIndex][remaining] = result
- Return result
- Return solve(0, amount)
Code
#include <vector>
using namespace std;
class Solution {
public:
int solve(vector<int>& coins, int ci, int rem, vector<vector<int>>& dp) {
if (rem == 0) return 1;
if (rem < 0 || ci == coins.size()) return 0;
if (dp[ci][rem] != -1) return dp[ci][rem];
int use = solve(coins, ci, rem - coins[ci], dp);
int skip = solve(coins, ci + 1, rem, dp);
return dp[ci][rem] = use + skip;
}
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<vector<int>> dp(n, vector<int>(amount + 1, -1));
return solve(coins, 0, amount, dp);
}
};class Solution:
def change(self, amount: int, coins: list[int]) -> int:
n = len(coins)
dp = [[-1] * (amount + 1) for _ in range(n)]
def solve(ci, rem):
if rem == 0:
return 1
if rem < 0 or ci == n:
return 0
if dp[ci][rem] != -1:
return dp[ci][rem]
use = solve(ci, rem - coins[ci])
skip = solve(ci + 1, rem)
dp[ci][rem] = use + skip
return dp[ci][rem]
return solve(0, amount)import java.util.Arrays;
class Solution {
private int solve(int[] coins, int ci, int rem, int[][] dp) {
if (rem == 0) return 1;
if (rem < 0 || ci == coins.length) return 0;
if (dp[ci][rem] != -1) return dp[ci][rem];
int use = solve(coins, ci, rem - coins[ci], dp);
int skip = solve(coins, ci + 1, rem, dp);
return dp[ci][rem] = use + skip;
}
public int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = new int[n][amount + 1];
for (int[] row : dp) Arrays.fill(row, -1);
return solve(coins, 0, amount, dp);
}
}Complexity Analysis
Time Complexity: O(n × amount)
There are n × (amount + 1) unique states, each computed at most once. Each computation does O(1) work (two recursive calls plus addition and a memo lookup). Total: O(n × amount).
Space Complexity: O(n × amount)
The 2D memo table stores n × (amount + 1) values. The recursion stack adds at most O(amount) depth (in the worst case, using coin=1 repeatedly). The dominant term is the memo table: O(n × amount).
Why This Approach Is Not Efficient
Memoization brings the time complexity to O(n × amount), which is efficient. However, the space usage is O(n × amount) for the 2D table plus O(amount) for the recursion stack.
For the given constraints (n ≤ 300, amount ≤ 5000), the memo table uses up to 300 × 5001 × 4 bytes ≈ 6 MB, which is acceptable but not minimal.
A critical observation enables further space optimization: when filling the DP table iteratively (bottom-up), to compute the row for coin i, we only need the current row (for the 'use' case, since we stay on the same coin) and the next row (for the 'skip' case). But actually, if we process coins one at a time and use a clever 1D array, we can reduce space to just O(amount). The trick is that for unbounded knapsack problems, iterating the amount in the forward direction (left to right) naturally allows reusing the same coin multiple times.
Optimal Approach - Space-Optimized Tabulation (1D DP)
Intuition
We replace the 2D table with a single 1D array dp where dp[j] represents the number of combinations to make amount j using the coins considered so far.
The key idea: we process one coin at a time. When we process coin c, for every amount j from c to amount, we update dp[j] += dp[j - c]. This adds the new combinations made possible by including one or more copies of coin c.
The reason we iterate left to right (from c to amount) instead of right to left is fundamental to this being an unbounded knapsack: we want to allow using the same coin multiple times. When computing dp[j], dp[j - c] may already include combinations using coin c in this same pass — that is exactly what we want, because we can use coin c again.
Contrast this with the 0/1 knapsack (like Count Partitions), where we iterate right to left to prevent reusing the same element. Here, reuse is the whole point.
The outer loop over coins (not over amounts) ensures we count combinations, not permutations. By fully processing coin 1 before moving to coin 2, we guarantee that each combination is counted exactly once.
Step-by-Step Explanation
Let's trace with amount = 5, coins = [1, 2, 5].
Step 1: Initialize dp = [1, 0, 0, 0, 0, 0]. dp[0] = 1 means there is one way to make amount 0: use no coins.
Step 2: Process coin = 1. For j from 1 to 5:
- j=1: dp[1] += dp[0] = 0 + 1 = 1
- j=2: dp[2] += dp[1] = 0 + 1 = 1
- j=3: dp[3] += dp[2] = 0 + 1 = 1
- j=4: dp[4] += dp[3] = 0 + 1 = 1
- j=5: dp[5] += dp[4] = 0 + 1 = 1
- dp = [1, 1, 1, 1, 1, 1]. Using only coin 1, there is exactly one way to make each amount.
Step 3: Process coin = 2. For j from 2 to 5:
- j=2: dp[2] += dp[0] = 1 + 1 = 2
- j=3: dp[3] += dp[1] = 1 + 1 = 2
- j=4: dp[4] += dp[2] = 1 + 2 = 3
- j=5: dp[5] += dp[3] = 1 + 2 = 3
- dp = [1, 1, 2, 2, 3, 3]. Now with coins {1, 2}: 2 ways for amount 2 ({1,1}, {2}), 3 ways for amount 4 ({1,1,1,1}, {1,1,2}, {2,2}), etc.
Step 4: Process coin = 5. For j from 5 to 5:
- j=5: dp[5] += dp[0] = 3 + 1 = 4
- dp = [1, 1, 2, 2, 3, 4].
Step 5: Answer = dp[5] = 4. The four combinations: {1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}.
1D DP — Counting Coin Combinations — Watch how the dp array evolves as we process each coin denomination left-to-right. The forward iteration allows reusing the same coin multiple times.
Algorithm
- Create a 1D array dp of size (amount + 1), initialized to 0
- Set dp[0] = 1 (one way to make amount 0)
- For each coin c in coins:
- For j from c to amount:
- dp[j] += dp[j - c]
- For j from c to amount:
- Return dp[amount]
Code
#include <vector>
using namespace std;
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] += dp[j - coin];
}
}
return dp[amount];
}
};class Solution:
def change(self, amount: int, coins: list[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for j in range(coin, amount + 1):
dp[j] += dp[j - coin]
return dp[amount]class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] += dp[j - coin];
}
}
return dp[amount];
}
}Complexity Analysis
Time Complexity: O(n × amount)
The outer loop iterates over n coins. For each coin, the inner loop runs over at most (amount + 1) values. Each iteration does O(1) work (one addition and one array access). Total: O(n × amount). With n ≤ 300 and amount ≤ 5000, this is at most 1,500,000 operations — extremely fast.
Space Complexity: O(amount)
We use a single 1D array of size (amount + 1). No recursion stack is needed since the approach is fully iterative. This is the minimum possible space — we need at least O(amount) to store the DP values for each amount from 0 to the target.