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 <= 5000Problem Overview: Given a list of coin denominations and a target amount, compute how many unique combinations of coins can make that amount. Each coin can be used unlimited times, and combinations with different orderings count as the same result.
Approach 1: Dynamic Programming with 2D Array (O(n × amount) time, O(n × amount) space)
This approach models the problem similarly to an unbounded knapsack. Use a 2D DP table dp[i][a] where i represents the first i coin types and a represents the current amount. For each state, you either exclude the current coin (dp[i-1][a]) or include it (dp[i][a - coin]) because coins can be reused. Iterating through coins and amounts fills the table and ensures every combination is counted exactly once. This method is easy to reason about and helpful when learning dynamic programming transitions.
Approach 2: Dynamic Programming with 1D Array (O(n × amount) time, O(amount) space)
The optimized version collapses the 2D DP table into a single array dp[a] representing the number of ways to form amount a. Initialize dp[0] = 1 since there is one way to make zero amount. Iterate through each coin first, then iterate amounts from the coin value up to the target. Update using dp[a] += dp[a - coin]. Processing coins in the outer loop prevents counting permutations like [1,2] and [2,1] separately, which is a key detail in combination problems involving arrays. This version reduces memory usage significantly while keeping the same time complexity.
Recommended for interviews: The 1D dynamic programming approach is the expected solution. It demonstrates strong understanding of dynamic programming state transitions and space optimization. Starting with the 2D formulation shows clear reasoning about the recurrence, while reducing it to 1D shows practical optimization skills interviewers look for.
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).
In the C implementation, we define a 2D array `dp` to represent the number of ways to achieve each possible amount (0 to `amount`) using the coins up to the current denomination. We iterate through every possible amount for each coin type, keeping the previously computed results.
Time Complexity: O(n*m), Space Complexity: O(n*m) where `n` is the `amount` and `m` is the number of coins.
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).
The C representation here manages a 1D array `dp` after consolidating lesser used states, promoting space efficiency while preserving the calculated subproblems on a single line at every stage of iteration.
Time Complexity: O(n*m), Space Complexity: O(n) where `n` is the `amount` and `m` is the number of coins.
We define f[i][j] as the number of coin combinations to make up the amount j using the first i types of coins. Initially, f[0][0] = 1, and the values of other positions are all 0.
We can enumerate the quantity k of the last coin used, then we have equation one:
$
f[i][j] = f[i - 1][j] + f[i - 1][j - x] + f[i - 1][j - 2 times x] + cdots + f[i - 1][j - k times x]
where x represents the face value of the i-th type of coin.
Let j = j - x, then we have equation two:
f[i][j - x] = f[i - 1][j - x] + f[i - 1][j - 2 times x] + cdots + f[i - 1][j - k times x]
Substituting equation two into equation one, we can get the following state transition equation:
f[i][j] = f[i - 1][j] + f[i][j - x]
The final answer is f[m][n].
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n$ are the number of types of coins and the total amount, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with 2D Array | Time Complexity: O(n*m), Space Complexity: O(n*m) where `n` is the `amount` and `m` is the number of coins. |
| Dynamic Programming with 1D Array | Time Complexity: O(n*m), Space Complexity: O(n) where `n` is the `amount` and `m` is the number of coins. |
| Dynamic Programming (Complete Knapsack) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with 2D Array | O(n × amount) | O(n × amount) | Best for understanding the DP state transition and building intuition for combination counting problems. |
| Dynamic Programming with 1D Array | O(n × amount) | O(amount) | Preferred solution when memory optimization matters and the standard approach expected in coding interviews. |
Coin Change 2 - Dynamic Programming Unbounded Knapsack - Leetcode 518 - Python • NeetCode • 184,384 views views
Watch 9 more video solutions →Practice Coin Change II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor