Coin Change II: Count Combinations for a Given Amount

83.7k
0

Given an array coins containing distinct positive denominations and a non-negative integer amount, find the number of different coin selections with a total value of amount.

Every denomination has an unlimited supply. Coin order does not create a new combination, so 1 + 2 and 2 + 1 represent the same choice. Return 0 when no combination reaches the target.

Example 1

Input: coins = [1, 2, 5], amount = 5
Output: 4
Explanation: The valid combinations are [5], [2, 2, 1], [2, 1, 1, 1], and [1, 1, 1, 1, 1].

Example 2

Input: coins = [2, 3], amount = 0
Output: 1
Explanation: The empty selection forms amount 0, so exactly one combination exists.

Recursion

Every coin type creates two choices: skip the current coin or take it. Skipping moves to the next smaller denomination, while taking reduces the remaining amount and keeps the same coin available. Keeping the same index after taking a coin allows unlimited reuse without changing the coin order.

The state solve(index, remaining) counts the number of combinations that form remaining using coin types from 0 through index. The initial call uses the last index and the full amount because every denomination is available at the beginning.

Algorithm

  • Start with solve(n - 1, amount) because the initial state includes every coin type and the complete target amount.

  • Return 1 when remaining == 0 because one valid combination has been formed.

  • Handle index == 0 using divisibility because repeated copies of the first denomination can form either one exact combination or none.

  • Move to index - 1 without changing remaining for the skip choice because the current coin type is no longer available.

  • Stay at the same index after subtracting coins[index] for the take choice because unlimited copies of the current denomination are allowed.

  • Add the skip and take results because the two choices represent disjoint combinations.

  • Return the result of solve(n - 1, amount) because this state considers all available denominations.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Counts ways for one index and remaining amount.
long long solve(int index, int remaining,
vector<int>& coins) {
// A zero remainder completes one combination.
if (remaining == 0) {
return 1;
}
// The first coin works only through exact division.
if (index == 0) {
return remaining % coins[0] == 0 ? 1 : 0;
}
// Skipping removes the current coin type.
long long notTaken = solve(index - 1, remaining, coins);
// A missing take branch contributes no combination.
long long taken = 0;
// Enough remainder permits another current coin.
if (coins[index] <= remaining) {
// Staying at the index allows unlimited reuse.
taken = solve(index, remaining - coins[index],
coins);
}
// Both branches contain disjoint combinations.
return notTaken + taken;
}
public:
// Returns the number of target-forming combinations.
long long change(int amount, vector<int>& coins) {
int n = coins.size();
// The last index initially exposes every coin type.
return solve(n - 1, amount, coins);
}
};
// Driver code
int main() {
vector<int> coins = {1, 2, 5};
int amount = 5;
Solution obj;
cout << obj.change(amount, coins) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(2(N + amount / minCoin)), where N is the number of coins, because the recursion can branch into skip and take choices across a maximum depth of N + amount / minCoin.

Space Complexity: O(N + amount / minCoin), because the deepest recursion path can skip every coin type and repeatedly take the smallest denomination.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Memoization

Direct recursion can reach the same index and remaining pair through different selections of larger coins. Recomputing every repeated state wastes work even though every future choice depends only on the same two values.

A two-dimensional dp array stores each finished answer. The recursive choices stay unchanged, while a cached value returns immediately during a later visit.

Algorithm

  • Begin with a dp table containing -1, so every untouched cell clearly marks an uncalculated state.

  • Keep solve(index, remaining) unchanged because the same coin prefix and remaining amount still define a complete subproblem.

  • Return the two base-case answers before cache access, so completed targets and first-coin divisibility need no stored entry.

  • Reuse dp[index][remaining] whenever a saved value exists, because another visit would repeat the same branch work.

  • Compute the skip branch at index - 1, so every combination without the current denomination remains covered.

  • Compute the take branch at the same index only for an affordable coin, so unlimited reuse stays valid without creating a negative amount.

  • Store the sum of both branches in dp[index][remaining], so later visits can return the completed count without repeated work.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Counts ways and stores every finished state.
long long solve(int index, int remaining,
vector<int>& coins,
vector<vector<long long>>& dp) {
// A zero remainder completes one combination.
if (remaining == 0) {
return 1;
}
// The first coin works only through exact division.
if (index == 0) {
return remaining % coins[0] == 0 ? 1 : 0;
}
// A saved state avoids repeated branch work.
if (dp[index][remaining] != -1) {
return dp[index][remaining];
}
// Skipping removes the current coin type.
long long notTaken = solve(
index - 1,
remaining,
coins,
dp
);
// A missing take branch contributes no combination.
long long taken = 0;
// Enough remainder permits another current coin.
if (coins[index] <= remaining) {
// Staying at the index allows unlimited reuse.
taken = solve(
index,
remaining - coins[index],
coins,
dp
);
}
// The cache stores both disjoint branch counts.
dp[index][remaining] = notTaken + taken;
// The stored count answers the current state.
return dp[index][remaining];
}
public:
// Returns the number of target-forming combinations.
long long change(int amount, vector<int>& coins) {
int n = coins.size();
// Minus one marks every state as uncalculated.
vector<vector<long long>> dp(
n,
vector<long long>(amount + 1, -1)
);
// The last index initially exposes every coin type.
return solve(n - 1, amount, coins, dp);
}
};
// Driver code
int main() {
vector<int> coins = {1, 2, 5};
int amount = 5;
Solution obj;
cout << obj.change(amount, coins) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × amount), where N is the number of coins, because at most N × (amount + 1) states are calculated once, with constant-time skip, take, and cache operations per state.

Space Complexity: O(N × amount + N + amount / minCoin), because the dp table stores all states, while the recursion stack can grow through skipped coins and repeated takes of the smallest coin.

Tabulation

Memoization already reveals every required state, so a table can build the same answers without recursive calls. Row index represents available coin types from 0 through index, and column currentAmount represents the amount being formed.

The skip value comes from the previous row. The take value comes from the current row at a smaller amount because the same coin stays available. Filling amounts from small to large guarantees the current-row take state already exists.

Algorithm

  • Begin with a table named dp containing n rows and amount + 1 columns, so every recursive state receives an iterative cell.

  • Mark every first-row amount divisible by coins[0] as 1, because repeated copies of the first denomination form exactly one combination.

  • Move through later coin indices from left to right, so the previous row already stores every skip result.

  • Process currentAmount from 0 through amount, so a smaller current-row amount is ready before another copy of the same coin is considered.

  • Read dp[index - 1][currentAmount] for the skip count because the previous row excludes the current denomination.

  • Read dp[index][currentAmount - coins[index]] for an affordable take because the current row preserves unlimited reuse.

  • Store the sum of skip and take counts, then return dp[n - 1][amount] because the final cell covers every coin and the complete target.

Dry Run

Coin Change II Tabulation

Coin Change II Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the number of target-forming combinations.
long long change(int amount, vector<int>& coins) {
int n = coins.size();
// Every cell stores one prefix-and-amount count.
vector<vector<long long>> dp(
n,
vector<long long>(amount + 1, 0)
);
// The first coin forms divisible amounts uniquely.
for (int currentAmount = 0;
currentAmount <= amount;
currentAmount++) {
// Divisibility gives one all-first-coin choice.
if (currentAmount % coins[0] == 0) {
dp[0][currentAmount] = 1;
}
}
// Each later row introduces one more coin type.
for (int index = 1; index < n; index++) {
// Forward amounts keep current-row takes ready.
for (int currentAmount = 0;
currentAmount <= amount;
currentAmount++) {
// The previous row skips the current coin.
long long notTaken =
dp[index - 1][currentAmount];
// A missing take contributes no combination.
long long taken = 0;
// Enough amount permits the current coin.
if (coins[index] <= currentAmount) {
// Current-row reuse keeps the coin active.
taken = dp[index][
currentAmount - coins[index]
];
}
// Both choices form disjoint combinations.
dp[index][currentAmount] =
notTaken + taken;
}
}
// The final cell covers all coins and the target.
return dp[n - 1][amount];
}
};
// Driver code
int main() {
vector<int> coins = {1, 2, 5};
int amount = 5;
Solution obj;
cout << obj.change(amount, coins) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × amount), where N is the number of coins, because every coin row processes all amount + 1 target states once.

Space Complexity: O(N × amount), because the two-dimensional dp table stores one count for every coin-prefix and amount pair, with no recursion stack.

Space Optimization

The tabulation row for a coin needs the saved skip count at the current amount and the already-updated take count at a smaller amount. A single dp array can hold both values because current amounts move forward.

For every coin, currentAmount starts at the coin value and grows toward amount. The variable currentWays adds the saved skip count and the active repeated-use count before the completed value shifts back into dp[currentAmount].

Algorithm

  • Begin with a one-dimensional dp array of length amount + 1, so every cell stores combinations for one amount using processed coin types.

  • Mark amounts divisible by the first denomination as 1, because repeated first coins form each divisible amount in exactly one way.

  • Move through later coin types in array order, so each combination gains denominations in one fixed order and cannot appear as a permutation.

  • Start currentAmount at the current coin value, because smaller amounts cannot include the current denomination.

  • Increase amounts from left to right, so dp[currentAmount - coin] already includes repeated uses of the active coin.

  • Calculate currentWays by adding the saved skip count and the active take count, because both choices form disjoint combinations.

  • Shift currentWays into dp[currentAmount], then return dp[amount] because the final cell includes every processed coin type.

Dry Run

Coin Change II Space Optimization

Coin Change II Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the number of target-forming combinations.
long long change(int amount, vector<int>& coins) {
// Every cell stores one amount count.
vector<long long> dp(amount + 1, 0);
// The first coin forms divisible amounts uniquely.
for (int currentAmount = 0;
currentAmount <= amount;
currentAmount++) {
// Divisibility gives one all-first-coin choice.
if (currentAmount % coins[0] == 0) {
dp[currentAmount] = 1;
}
}
// Each pass introduces one more coin type.
for (int index = 1;
index < coins.size();
index++) {
// Forward updates keep current-coin reuse ready.
for (int currentAmount = coins[index];
currentAmount <= amount;
currentAmount++) {
// Current ways combine skip and take counts.
long long currentWays =
dp[currentAmount] +
dp[currentAmount - coins[index]];
// Shift the current count into the active row.
dp[currentAmount] = currentWays;
}
}
// The target cell contains every combination.
return dp[amount];
}
};
// Driver code
int main() {
vector<int> coins = {1, 2, 5};
int amount = 5;
Solution obj;
cout << obj.change(amount, coins) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × amount), where N is the number of coins, because each coin processes every reachable amount at most once.

Space Complexity: O(amount), because one dp array stores the best count for every amount, with no recursion stack or second row.

Interview follow-up Questions

No. Equal denomination counts form the same combination, so 1 + 2 and 2 + 1 contribute only once.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock IV: At Most K Transactions

Given an integer k and an array prices , prices[day] stores the stock price on a particular day. At most k transactions may be completed. One transaction contains one buy followed by...

50.8k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Comments0