Problem Explanation

Given a list of coins of different denominations and a total amount of money, the goal is to find the total number of ways the coins can be combined to result in the given amount.

For example, using the denominations [1,2,5] with a total amount of 5, there are four possible combinations:

• 5 = 5
• 5 = 2+2+1
• 5 = 2+1+1+1
• 5 = 1+1+1+1+1

On the other hand, using the denomination [2] with a total amount of 3, no combination can form the total amount of 3.

Therefore, the output should be the total number of combinations that can form the given amount.

Solution Approach

The solution uses Dynamic Programming. It builds up the solution by solving sub-problems i.e., it checks for each coin, if including it in the solution increases the number of ways or not.

The coins are iterated over and for each coin, the goal is to build the solution up to the target amount.

At the start, the number of combinations for forming a sum 0 is 1, i.e., by using no coin (an empty combination).

To build the solution, for each coin, it is considered that it is included in the sum. The remaining sum is obtained by subtracting the current coin value from the target sum. The number of ways these remaining sums can be obtained is updated.

Java Solution

1
2java
3class Solution {
4    public int change(int amount, int[] coins) {
5        int[] dp = new int[amount + 1];
6        dp[0] = 1;
7
8        for (int coin : coins) {
9            for (int i = coin; i <= amount; i++) {
10                dp[i] += dp[i - coin];
11            }
12        }
13
14        return dp[amount];
15    }
16}

Here, a dp array is defined to store the number of combinations to reach the sum at every index. It starts by initializing dp[0] (the number of combinations for amount 0) to 1. It then iterates over each coin and for each coin, it adds how many more ways the sum can be achieved given this coin.

JavaScript Solution

1
2javascript
3var change = function(amount, coins) {
4    const dp = Array(amount + 1).fill(0);
5    dp[0] = 1;
6
7    for (let coin of coins) {
8        for (let i = coin; i <= amount; i++) {
9            dp[i] += dp[i - coin];
10        }
11    }
12    return dp[amount];
13};

In JavaScript, the same logic is implemented. An Array 'dp' corresponds to the dp array in the Java version.

Python Solution

1
2python
3class Solution:
4    def change(self, amount: int, coins: List[int]) -> int:
5        dp = [0] * (amount + 1)
6        dp[0] = 1
7
8        for coin in coins:
9            for x in range(coin, amount + 1):
10                dp[x] += dp[x - coin]
11
12        return dp[amount]

Similar to the previous solutions, here a Python list 'dp' is initialized with zeros, with the size equivalent to the amount plus one. Then the solutions to the sub-problems are built up similarly.

C++ Solution

1
2c++
3class Solution {
4public:
5    int change(int amount, vector<int>& coins) {
6        vector<int> dp(amount + 1, 0);
7        dp[0] = 1;
8
9        for (int coin : coins) {
10            for (int i = coin; i <= amount; i++) {
11                dp[i] += dp[i - coin];
12            }
13        }
14
15        return dp[amount];
16    }
17};

The C++ version follows the same pattern, replacing python's list and JavaScript's array with C++'s vector.

C# Solution

1
2csharp
3public class Solution {
4    public int Change(int amount, int[] coins) {
5        int[] dp = new int[amount + 1];
6        dp[0] = 1;
7
8        foreach (int coin in coins) {
9            for (int i = coin; i <= amount; i++) {
10                dp[i] += dp[i - coin];
11            }
12        }
13        
14        return dp[amount];
15    }
16}

The C# version also uses an integer array for memoization. Each entry in the array represents the number of ways to make that amount. It iterates through the values, and for each coin, updates the ways to make values greater than or equal to that coin.# Ruby Solution

1
2ruby
3def change(amount, coins)
4    dp = Array.new(amount + 1, 0)
5    dp[0] = 1
6
7    coins.each do |coin|
8        (coin..amount).each do |i|
9            dp[i] += dp[i - coin]
10        end
11    end
12    dp[amount]
13end

In the Ruby version, it follows the same dynamic programming approach as other solutions. It starts by creating an array 'dp' with size 'amount + 1' initializing all elements to 0 but making the first element as 1. It then iterates over each coin and for each coin, it calculates the number of combinations for all values from that coin up to the given amount.

Kotlin Solution

1
2kotlin
3fun change(amount: Int, coins: IntArray): Int {
4    val dp = IntArray(amount + 1) { 0 }
5    dp[0] = 1
6    for (coin in coins) {
7        for (i in coin..amount) {
8            dp[i] += dp[i - coin]
9        }
10    }
11    return dp[amount]
12}

The Kotlin solution is also quite similar to other solutions. The dp array is created with Kotlin's IntArray constructor and all the values are initially set to 0 and dp[0] is later set to 1. Then it loops through every coin and for each coin, it counts the number of ways to make up amounts from the value of the coin to the target amount by adding the ways to the amount with the coin subtracted.

Swift Solution

1
2swift
3func change(_ amount: Int, _ coins: [Int]) -> Int {
4    var dp = Array(repeating: 0, count: amount + 1)
5    dp[0] = 1
6    
7    for coin in coins {
8        for i in coin ... amount {
9            dp[i] += dp[i-coin]
10        }
11    }
12    return dp[amount]
13}

In Swift, we use "Array(repeating: count:)" to create an array with a specific count and an initial repeating value. This array 'dp' is used to keep track of the number of ways to achieve a certain amount. The rest of the function works similarly to the solutions in other programming languages, iterating over the coin array and updating the number of ways to form the amounts from the coin value to the total amount.

Overall, the dynamic programming approach enables us to solve this problem efficiently in various programming languages by decomposing the problem into simpler sub-problems and using the solutions to these sub-problems to build up the solution to the larger problem.