Algorithm
Problem Name: 518. Coin Change II
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
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public static int change(int amount, int[] coins) {
int[] combinations = new int[amount+1];
combinations[0] = 1;
for (int coin : coins) {
for (int i=coin; i < amount+1; i++) {
combinations[i] += combinations[i-coin];
}
}
return combinations[amount];
}
}
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
function change(amount, coins) {
const dp = Array.from(new Array(coins.length + 1), () =>
new Array(amount + 1).fill(0)
)
dp[0][0] = 1
for (let i = 1; i < = coins.length; i++) {
dp[i][0] = 1
for (let j = 1; j < = amount; j++) {
dp[i][j] =
dp[i - 1][j] + (j >= coins[i - 1] ? dp[i][j - coins[i - 1]] : 0)
}
}
return dp[coins.length][amount]
}
Copy The Code &
Try With Live Editor
Input
Output
#3 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0518_CoinChange2
{
public int Change(int amount, int[] coins)
{
var dp = new int[amount + 1];
dp[0] = 1;
foreach (var coin in coins)
for (int x = coin; x < = amount; x++)
dp[x] += dp[x - coin];
return dp[amount];
}
}
}
Copy The Code &
Try With Live Editor
Input