Coin Change II - Solution & Explanation
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 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] <= 5000- All the values of
coinsare unique. 0 <= amount <= 5000
Approach Overview
Problem 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.
Approach 1: Dynamic Programming with 2D Array
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.
Complexity
Time Complexity: O(n*m), Space Complexity: O(n*m) where `n` is the `amount` and `m` is the number of coins.
Approach 2: Dynamic Programming with 1D Array
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.
Complexity
Time Complexity: O(n*m), Space Complexity: O(n) where `n` is the `amount` and `m` is the number of coins.
Approach 3: Dynamic Programming (Complete Knapsack)
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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) | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Coin Change 2 - Dynamic Programming Unbounded Knapsack - Leetcode 518 - Python • NeetCode • 192,546 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Coin Change II easy or hard?
What is the best approach for Coin Change II?
How to solve Coin Change II in O(n × amount)?
What data structure is used in Coin Change II?
What is the time complexity of Coin Change II?
Coin Change II Python or Java solution approach?
Is Coin Change II asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Coin Change II with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor