518. Coin Change II
Problem Description
The problem provides an array called coins
which contains integers representing the denominations of different coins. In addition, you are given an integer amount
which signifies the total amount of money you need to create using these coins. The question is to find out the total number of distinct combinations of coins that can add up to exactly that amount
. If it is not possible to get to that amount
using the given coins, the function should return 0
. Notably, it is assumed that you have an unlimited supply of each coin denomination in the array coins
.
The answer needs to be such that it can fit within a 32-bit signed integer, effectively suggesting that the solution does not need to handle extremely large numbers that exceed this size.
Intuition
The solution requires a methodical approach to count the combinations without having to consider each one explicitly, which would be inefficient. This is where dynamic programming becomes useful. Dynamic programming is a strategy for solving complex problems by breaking them down into simpler subproblems, solving each subproblem just once, and storing their solutions – ideally, using a memory-based data structure.
The intuition for the solution arises from realizing that the problem resembles the classic "Complete Knapsack Problem". With the knapsack problem, imagine you have a bag (knapsack) and you aim to fill it with items (in this case, coins) up to a certain weight limit (the amount
), and you are interested in counting the number of ways to reach exactly that limit.
-
We use a list
dp
to store the number of ways to reach every amount from0
toamount
. So,dp[x]
will indicate how many distinct combinations of coins can sum up to the valuex
. -
Initialize the
dp
list with zeros since initially, we have no coin, so there are zero ways to reach any amount except for0
. For an amount of0
, there is exactly one way to reach it – by choosing no coins. This meansdp[0]
is initialized to1
. -
Iterate over each coin in
coins
, considering it as a potential candidate for making up theamount
. For each coin, update thedp
list. -
For each value from the
coin
's denomination up toamount
, incrementdp[j]
bydp[j - coin]
. This represents that the number of combinations for an amountj
includes all the combinations we had foramount (j - coin)
plus this coin.
By filling the dp
list iteratively and using the previously computed values, we build up the solution without redundant calculations and eventually dp[amount]
gives us the total number of combinations to form amount
using the given denominations.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation of the solution is grounded in the dynamic programming approach. To better understand the solution, let's take a detailed look at each step that is performed in the provided code:
-
A dynamic programming array
dp
is initiated with a length of one more than theamount
, because we need to store ways to reach amounts ranging from0
toamount
inclusively. Every entry indp
is set to0
to start.1dp = [0] * (amount + 1)
-
To establish our base case,
dp[0]
is set to1
, because there is always exactly one way to reach an amount of0
— by not using any coins.1dp[0] = 1
-
The primary loop iterates over each
coin
in thecoins
array. This loop is necessary to consider each coin denomination for making up different amounts.1for coin in coins: 2 # loop body
-
Within this loop, a nested loop runs from
coin
(the current coin's value) up toamount + 1
. This loop updatesdp[j]
wherej
is the current target amount being considered. It is important we start atcoin
because that is the smallest amount that can be made with the currentcoin
denomination, and previous amounts would have been evaluated already with the other coins.1for j in range(coin, amount + 1): 2 dp[j] += dp[j - coin]
-
With each iteration of the inner loop,
dp[j]
is increased bydp[j - coin]
. The reasoning behind this is the essence of dynamic programming where we use previously computed results to construct the current result. In this aspect, ifdp[j - coin]
represents the number of ways to reachj - coin
amount, then we are effectively saying if you add the currentcoin
to all those combinations, you now reachj
. This way we are adding to the count of reachingj
with all the ways that existed to reachj - coin
.
Following these steps, dp[amount]
eventually holds the total number of combinations that can be used to reach the amount
, and thus, is returned as the final answer:
1return dp[-1]
This dynamic programming table (dp
array) allows us to avoid re-calculating combinations for smaller amounts, making the algorithm efficient and scalable for large inputs. By relying on the iterative addition of combinations, the algorithm effectively builds the solution from the ground up, solving smaller sub-problems before piecing them together to yield the solution for the larger problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we're given coins = [1, 2, 5]
and amount = 5
. We want to find the total number of distinct combinations that can add up to the amount
.
-
Initialize the dynamic programming array
dp
: Create adp
array of sizeamount + 1
, which in this case is6
because our target amount is5
. Initially, it will look like this after initialization:1dp = [0, 0, 0, 0, 0, 0]
-
Establish the base case: Since there's only one way to reach
0
(using no coins), we setdp[0]
to1
:1dp = [1, 0, 0, 0, 0, 0]
-
Iterate over each
coin
incoins
:- Start with the first coin
1
. For each amount from1
to5
(amount + 1
), we add the number of combinations without using the coin (already stored indp
) to the number of ways to make the current amount using this coin.
1For coin = 1: 2dp = [1, 1+dp[0], 1+dp[1], 1+dp[2], 1+dp[3], 1+dp[4]] 3After iteration: dp = [1, 1, 1, 1, 1, 1]
- For coin
2
, we start at amount2
and update thedp
array similarly.
1For coin = 2: 2dp = [1, 1, 1+dp[0], 1+dp[1], 1+dp[2], 1+dp[3]] 3After iteration: dp = [1, 1, 2, 2, 3, 3]
- Lastly, for
5
, we start at amount5
, as it is the only value that can be updated by a coin of denomination5
.
1For coin = 5: 2dp = [1, 1, 2, 2, 3, 3+dp[0]] 3After iteration: dp = [1, 1, 2, 2, 3, 4]
- Start with the first coin
-
Result: The final
dp
array represents the number of ways to make each amount up to5
.dp[5]
is our answer because it's the number of combinations that make up the amount5
.1dp = [1, 1, 2, 2, 3, 4]
So, there are 4
distinct combinations that can add up to 5
using the denominations [1, 2, 5]
. These combinations are:
1 + 1 + 1 + 1 + 1
(five 1's)1 + 1 + 1 + 2
(three 1's and one 2)1 + 2 + 2
(one 1 and two 2's)5
(one 5)
In Python, the final result would be obtained by returning the last element of the dp
array:
1return dp[-1]
Solution Implementation
1# Importing typing module to use the List type annotation.
2from typing import List
3
4class Solution:
5 def change(self, amount: int, coins: List[int]) -> int:
6 # Initializing a list `dp` to store the number of ways to make change for
7 # each value from 0 up to the given `amount`.
8 dp = [0] * (amount + 1)
9
10 # There is 1 way to make change for 0 amount: use no coins
11 dp[0] = 1
12
13 # Iterate over each coin in coins list
14 for coin in coins:
15 # For each `coin` value, update `dp` for all amounts that are greater
16 # than or equal to the current `coin`.
17 for current_amount in range(coin, amount + 1):
18 # The number of ways to create the current amount includes the number
19 # of ways to create the amount that is the current amount minus the
20 # value of the current coin.
21 dp[current_amount] += dp[current_amount - coin]
22
23 # Return the last element in dp which contains the number of ways
24 # to make change for the original `amount` using the given `coins`.
25 return dp[-1]
26
1class Solution {
2 public int change(int amount, int[] coins) {
3 // dp array to store the number of ways to make change for each amount
4 int[] dp = new int[amount + 1];
5
6 // There is 1 way to make change for the amount zero, that is to choose no coins
7 dp[0] = 1;
8
9 // Iterate over each type of coin
10 for (int coin : coins) {
11 // Update the dp array for all amounts that can be reached with the current coin
12 for (int currentAmount = coin; currentAmount <= amount; currentAmount++) {
13 // The number of ways to make change for currentAmount includes the number of ways
14 // to make change for (currentAmount - coin value)
15 dp[currentAmount] += dp[currentAmount - coin];
16 }
17 }
18
19 // Return the total number of ways to make change for the specified amount
20 return dp[amount];
21 }
22}
23
1class Solution {
2public:
3 // The function "change" computes the number of ways to make up the amount
4 // with the given set of coin denominations.
5 int change(int amount, vector<int>& coins) {
6 // dp is the dynamic programming table where dp[i] will store
7 // the number of ways to make up the amount i.
8 vector<int> dp(amount + 1, 0);
9
10 // There is one way to make amount 0, which is not using any coins.
11 dp[0] = 1;
12
13 // Iterate over each type of coin.
14 for (int coin : coins) {
15 // For each coin, update the dp table for all amounts from coin to 'amount'.
16 for (int currentAmount = coin; currentAmount <= amount; ++currentAmount) {
17 // The number of ways to make up currentAmount includes the number of ways
18 // to make (currentAmount - coin), as we can add the current coin
19 // to those combinations to get currentAmount.
20 dp[currentAmount] += dp[currentAmount - coin];
21 }
22 }
23
24 // Return the total number of ways to make up the original amount.
25 return dp[amount];
26 }
27};
28
1function change(amount: number, coins: number[]): number {
2 // Create a dp array to store the number of ways to make change for each amount from 0 to amount
3 let waysToMakeChange = new Array(amount + 1).fill(0);
4
5 // There is 1 way to make change for amount 0, which is to use no coins
6 waysToMakeChange[0] = 1;
7
8 // Iterate over each coin
9 for (let coin of coins) {
10 // For each coin, update the ways to make change for amounts greater than or equal to the coin value
11 for (let currentAmount = coin; currentAmount <= amount; ++currentAmount) {
12 // The number of ways to make change for the current amount is increased by the number of ways
13 // to make change for the amount that remains after using this coin (currentAmount - coin)
14 waysToMakeChange[currentAmount] += waysToMakeChange[currentAmount - coin];
15 }
16 }
17
18 // After filling the dp array, the last element holds the number of ways to make change for the original amount
19 return waysToMakeChange.pop(); // Return the last element of the waysToMakeChange array
20}
21
Time and Space Complexity
The given code is a dynamic programming solution that calculates the number of ways to make up a certain amount using the given denominations of coins.
Time Complexity:
To determine the time complexity, we need to consider the two nested loops in the code:
- The outer loop runs once for each coin in the
coins
list. Let's assume the number of coins isn
. - The inner loop runs for each value from
coin
up toamount
. In the worst case, this will run from1
toamount
, which we represent asm
.
For each combination of a coin and an amount, the algorithm performs a constant amount of work by updating the dp
array. Therefore, the total number of operations is proportional to the number of times the inner loop runs times the number of coins, which is O(n*m)
.
So, the time complexity is O(n*m)
where n
is the number of coins, and m
is the amount.
Space Complexity:
The space complexity is determined by the size of the data structures used in the code. Here, there is one primary data structure, the dp
array, which has a size of amount + 1
. No other data structures depend on n
or m
.
Therefore, the space complexity is O(m)
, where m
is the amount.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.