In this guide, you will get 518. Coin Change II LeetCode Solution with the best time and space complexity. The solution to Coin Change II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000
Complexity Analysis
Time Complexity: O(|\texttt{coins}| \cdot \texttt{amount})
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1);
dp[0] = 1;
for (const int coin : coins)
for (int i = coin; i <= amount; ++i)
dp[i] += dp[i - coin];
return dp[amount];
}
}; /* code provided by PROGIEZ */
518. Coin Change II LeetCode Solution in Java
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (final int coin : coins)
for (int i = coin; i <= amount; ++i)
dp[i] += dp[i - coin];
return dp[amount];
}
} // code provided by PROGIEZ
518. Coin Change II LeetCode Solution in Python
class Solution:
def change(self, amount: int, coins: list[int]) -> int:
dp = [1] + [0] * amount
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount] # code by PROGIEZ
