Coin Change II solution and explanation
Mastercard
Google
9 more videos on this problem
Coin Change 2 - Dynamic Programming Unbounded Knapsack - Leetcode 518 - PythonNeetCode · 23:19 · 192K views
Coin Change 2 | Dynamic programming | Leetcode #518Techdose · 20:32 · 58K views
Coin Change II | Made Super Easy | Recursion | Memoization | AMAZON | Leetcode-518codestorywithMIK · 24:32 · 23K views
[Java] Leetcode 518. Coin Change 2 [DP Distinct Ways #8]Eric Programming · 18:24 · 1K views
518. Coin Change II - LeetCode Python SolutionCode with Carter · 9:32 · 1K views
Coin Change II | LeetCode 518 DP ExplainedDestination FAANG · 13:50 · 937 views
Unlocking the Secrets of Dynamic Programming in Rust | LeetCode 518. Coin Change II - Live CodingvanAmsen · 6:14 · 491 views
Coin Change II Problem Explained | Number of Ways with Dynamic Programming | LeetCode 518Baa Code Education · 3:04 · 403 views
Daily Leetcode #1228: Aug 11, 2023 - 518. Coin Change IIProgramming Live with Larry · 13:43 · 393 views
Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode)Back To Back SWE · 11:42 · 180K views
The problem
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).
def change(amount, coins):
dp = [[0] * (amount + 1) for _ in range(len(coins) + 1)]
for i in range(len(coins) + 1):
dp[i][0] = 1
for i in range(1, len(coins) + 1):
for j in range(1, amount + 1):
dp[i][j] = dp[i-1][j]
if j >= coins[i-1]:
dp[i][j] += dp[i][j-coins[i-1]]
return dp[len(coins)][amount]
print(change(5, [1, 2, 5])) # Output: 4import java.util.Arrays;
public class CoinChange {
public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length + 1][amount + 1];
for (int i = 0; i <= coins.length; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= coins.length; i++) {
for (int j = 1; j <= amount; j++) {
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;
System.out.println("Number of combinations: " + cc.change(amount, coins));
}
}#include <vector>
#include <iostream>
using namespace std;
int change(int amount, vector<int>& coins) {
vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, 0));
for (int i = 0; i <= coins.size(); i++) {
dp[i][0] = 1;
}
for (size_t i = 1; i <= coins.size(); i++) {
for (int j = 1; j <= amount; j++) {
dp[i][j] = dp[i-1][j];
if (j >= coins[i-1]) {
dp[i][j] += dp[i][j - coins[i-1]];
}
}
}
return dp[coins.size()][amount];
}
int main() {
vector<int> coins = {1, 2, 5};
int amount = 5;
cout << "Number of combinations: " << change(amount, coins) << endl;
return 0;
}function change(amount, coins) {
let dp = Array(coins.length + 1).fill(0).map(() => Array(amount + 1).fill(0));
for (let i = 0; i <= coins.length; i++) {
dp[i][0] = 1;
}
for (let i = 1; i <= coins.length; i++) {
for (let j = 1; j <= amount; j++) {
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];
}
console.log(change(5, [1, 2, 5])); // Output: 4#include <stdio.h>
int change(int amount, int* coins, int coinsSize) {
int dp[coinsSize + 1][amount + 1];
for (int i = 0; i <= coinsSize; i++) {
dp[i][0] = 1;
}
for (int j = 1; j <= amount; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= coinsSize; i++) {
for (int j = 1; j <= amount; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= coins[i - 1]) {
dp[i][j] += dp[i][j - coins[i - 1]];
}
}
}
return dp[coinsSize][amount];
}
int main() {
int coins[] = {1, 2, 5};
int amount = 5;
printf("Number of combinations: %d\n", change(amount, coins, 3));
return 0;
}using System;
public class CoinChange {
public int Change(int amount, int[] coins) {
int[,] dp = new int[coins.Length + 1, amount + 1];
for (int i = 0; i <= coins.Length; i++) {
dp[i, 0] = 1;
}
for (int i = 1; i <= coins.Length; i++) {
for (int j = 1; j <= amount; j++) {
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));
}
}In Python, the 2D list `dp` allows us to handle subproblem results for dynamic programming. We consider each coin and all amounts achievable with prior denominations, accumulating solutions from previously calculated states.
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).
def change(amount, coins):
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]
print(change(5, [1, 2, 5])) # Output: 4import java.util.Arrays;
public class CoinChange {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
public static void main(String[] args) {
CoinChange cc = new CoinChange();
int[] coins = {1, 2, 5};
int amount = 5;
System.out.println("Number of combinations: " + cc.change(amount, coins));
}
}#include <vector>
#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;
}function change(amount, coins) {
let dp = Array(amount + 1).fill(0);
dp[0] = 1;
for (let coin of coins) {
for (let j = coin; j <= amount; j++) {
dp[j] += dp[j - coin];
}
}
return dp[amount];
}
console.log(change(5, [1, 2, 5])); // Output: 4#include <stdio.h>
int change(int amount, int* coins, int coinsSize) {
int dp[amount + 1];
for (int i = 0; i <= amount; i++) dp[i] = 0;
dp[0] = 1;
for (int i = 0; i < coinsSize; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
int main() {
int coins[] = {1, 2, 5};
int amount = 5;
printf("Number of combinations: %d\n", change(amount, coins, 3));
return 0;
}using System;
public class CoinChange {
public int Change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 0; i < coins.Length; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[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));
}
}Python reduces space use to a 1-dimensional array `dp`, fully opting in to utilize prior solutions by adding coin contributions directly into new entries without need for a secondary dimension.
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.
function change(amount: number, coins: number[]): number {
const [m, n] = [coins.length, amount];
const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i <= m; ++i) {
for (let j = 0; j <= n; ++j) {
f[i][j] = f[i - 1][j];
if (j >= coins[i - 1]) {
f[i][j] += f[i][j - coins[i - 1]];
}
}
}
return f[m][n];
}func change(amount int, coins []int) int {
m, n := len(coins), amount
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
f[0][0] = 1
for i := 1; i <= m; i++ {
for j := 0; j <= n; j++ {
f[i][j] = f[i-1][j]
if j >= coins[i-1] {
f[i][j] += f[i][j-coins[i-1]]
}
}
}
return f[m][n]
}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) | – |
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. |
Frequently asked questions
Is Coin Change II easy or hard?
Coin Change II is considered a Medium difficulty problem. The challenge is recognizing it as a combination-counting dynamic programming problem and avoiding permutation counting by iterating coins before amounts.
What is the best approach for Coin Change II?
The best approach uses dynamic programming with a 1D array. Iterate through each coin and update a DP array where dp[a] stores the number of ways to form amount a. The algorithm runs in O(n × amount) time and O(amount) space, which is optimal for this problem.
How to solve Coin Change II in O(n × amount)?
Use dynamic programming. Initialize dp[0] = 1 and iterate through each coin. For every amount from coin value to target, update dp[a] += dp[a - coin]. This counts combinations while preventing permutation duplicates.
What data structure is used in Coin Change II?
The core data structure is a dynamic programming array. Either a 2D table dp[i][amount] or a space‑optimized 1D array dp[amount] is used to store the number of ways to build each amount using available coins.
What is the time complexity of Coin Change II?
The standard dynamic programming solution runs in O(n × amount) time, where n is the number of coin types and amount is the target value. Each coin iterates through all amounts once, updating the number of combinations.
Coin Change II Python or Java solution approach?
Python and Java implementations typically use the 1D DP approach. Initialize an array dp of size amount + 1, set dp[0] = 1, then iterate through each coin and update dp[a] += dp[a - coin] for valid amounts.
Is Coin Change II asked at Google, Amazon, or Meta?
Coin Change II appears frequently in coding interviews at companies like Amazon, Google, and Meta because it tests dynamic programming fundamentals, especially the unbounded knapsack pattern and DP state transitions.