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 the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10] Output: 1
Constraints:
1 <= coins.length <= 3001 <= coins[i] <= 5000coins are unique.0 <= amount <= 5000Coin Change II asks you to count how many different combinations of given coin denominations can make up a target amount. Unlike the classic coin change problem that minimizes coins, this version focuses on counting combinations. A common way to approach it is with Dynamic Programming.
Define a DP state where dp[i] represents the number of ways to form amount i. By iterating through each coin and updating the DP array for all reachable amounts, you ensure combinations are counted without duplicating different orderings of the same set of coins. The key idea is to process coins in the outer loop and amounts in the inner loop so that each coin contributes to new combinations correctly.
You can first reason about the problem using a 2D DP formulation (coins vs. amount) and then optimize it to a 1D DP array for better space efficiency. This optimized approach runs in O(n × amount) time with O(amount) space, where n is the number of coin types.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| 2D Dynamic Programming | O(n × amount) | O(n × amount) |
| Optimized 1D Dynamic Programming | O(n × amount) | O(amount) |
NeetCode
This method involves using a 2D array to keep track of number of ways to make up a certain amount using coins up to a particular denomination. The rows in the array represent the number of coins available (up to that index), and the columns represent each possible amount up to the target.
Define dp[i][j] as the number of ways to make amount j using the first i types of coins. Initialize dp[i][0] to 1 since there is one way to make amount 0 (choosing no coin). For each coin, iterate over all amounts and accumulate the number of ways by including the current coin.
Time complexity is O(n*m) where n is the amount and m is the number of coins. Space complexity is also O(n*m).
Time Complexity: O(n*m), Space Complexity: O(n*m) where `n` is the `amount` and `m` is the number of coins.
1using System;
2
3public class CoinChange {
4 public int Change(int amount, int[] coins) {
5 int[,] dp = new int[coins.Length + 1, amount + 1];
6 for (int i = 0; i <= coins.Length; i++) {
7 dp[i, 0] = 1;
8 }
9 for (int i = 1; i <= coins.Length; i++) {
10 for (int j = 1; j <= amount; j++) {
11 dp[i, j] = dp[i - 1, j];
if (j >= coins[i - 1]) {
dp[i, j] += dp[i, j - coins[i - 1]];
}
}
}
return dp[coins.Length, amount];
}
public static void Main(string[] args) {
CoinChange cc = new CoinChange();
int[] coins = { 1, 2, 5 };
int amount = 5;
Console.WriteLine("Number of combinations: " + cc.Change(amount, coins));
}
}For C#, a 2D array double precision table aids in dynamically computing solutions to subproblems based on the coin additions and respective amounts, stored optimally during iteration.
This method optimizes space usage by employing a 1D array to store results. It iterates over each coin and updates the number of ways for each possible amount.
Define dp[j] as the number of ways to make amount j. Initially, set dp[0] to 1 (to denote the empty set that sums up to zero). Iterate through each coin, then iterate over possible amounts in nested for-loops from current coin's value to amount, updating the dp array by adding ways from previous calculations.
Time complexity remains O(n*m), but space complexity improves to O(n).
Time Complexity: O(n*m), Space Complexity: O(n) where `n` is the `amount` and `m` is the number of coins.
#include <iostream>
using namespace std;
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (size_t i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
int main() {
vector<int> coins = {1, 2, 5};
int amount = 5;
cout << "Number of combinations: " << change(amount, coins) << endl;
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Coin Change II problem are commonly asked in technical interviews at major tech companies. It tests understanding of dynamic programming, state transitions, and how to avoid counting duplicate permutations.
A dynamic programming array is the most suitable data structure for this problem. Typically a 1D integer array is used where dp[i] stores the number of ways to make amount i. This structure enables efficient updates while iterating through coins.
The optimal approach uses dynamic programming. By maintaining a DP array where each index represents the number of ways to form a specific amount, you can iteratively update it using each coin denomination. Processing coins first ensures combinations are counted without duplicates.
Coin Change I focuses on finding the minimum number of coins required to reach a target amount. Coin Change II, on the other hand, asks for the total number of distinct combinations that can produce the target amount using unlimited coins.
Reduction to a 1D array `dp` occurs in the C++ solution, seamlessly upgrading space efficiency by consolidating state solutions as soon as possible while iteratively resolving each sum creation using the current coin.