## 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 &

Input

cmd
amount = 5, coins = [1,2,5]

Output

cmd
4

### #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 &

Input

cmd
amount = 5, coins = [1,2,5]

Output

cmd
4

### #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 &

Input

cmd
amount = 3, coins = [2]