🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

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

Solution:

This problem can be thought of as follows:

• Maximum amount given in this problem is analogous to maximum knapsack weight capacity in the knapsack problem.
• We can use as many instances of each coin as needed. So it is a knapsack problem, it would be Unbounded version of the knapsack problem.
• For every coin we have option to either include that coin (one or more instances) or not include at all.
• All the coins in each combination should make up the exact amount. So it would be similar to filling a knapsack with weight equal to the maximum capacity. If maximum weight capacity of knapsack is W then we would have to put items of weight = W, and any less or more.

From the above discussion it is clear that the given problem can be solved using the concept of Unbounded Knapsack Problem. I have put more details in the inline comments in the code below:

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Space Optimization:

In the above solution we see that dp[current_coin_index][current_amount] depends on dp[current_coin_index - 1][current_amount] and dp[current_coin_index][current_amount - coins[current_coin_index]]. So at any point of time we ony need only rely on dp[current_coin_index - 1][current_amount] and dp[current_coin_index][current_amount - coins[current_coin_index]]. So, at any point of time if we are at amount = A and processing coins[i] we need the "total number of combinations possible for amount = A for coins[0...(i - 1)]" a "total number of combinations possible for the same coin index coins[0...i] for any amount lesser than current amount". This means we can start from index 0 of coins array and going computing till index = (n - 1). For each index we would be computing the the dp values of all possible amounts (0 to max amount).
So if dp[a] gives us the total number of possible combinations for amount = a for certain length of coins[] array, the below code computes the desired result:

for (int len = 1; len <= coins.length; len++) {
            for (int weight = 1; weight <= amount; weight++) { 
                if (weight - coins[len - 1] >= 0) {
                    dp[weight] += dp[weight - coins[len - 1]]; 
                }
            }
        }

Below is the complete solution with space optimization:

Java Code:

Please subscribe to access the Code.
After your successful login, please come back and refresh this page.

Python Code:

Login to Access Content




Important note about the nested for-loop in the code above:
If the outer loop is on amount and inner loop on coins that would NOT give correct result, i.e, the below code would give incorrect result:

for (int amt = 1; amt <= amount; amt++) {
    for (int len = 1; len <= coins.length; len++) {
        if (amt - coins[len - 1] >= 0) {
            dp[amt] += dp[amt - coins[len - 1]]; 
        }
    }
}

Since in every iteration we are reusing value of dp[j] from previous step, while computing dp[j] we cannot just use value of dp[j] for coins[0...(n - 1)] for coin index != (n- 1). If we are counting for k-th coin the value of dp[j] has to be for coins[0....(k - 1)] and not for the entire coins array. What I mean for this is when we are computing dp value for subarray weights[0...(k - 1)] we should not involve items from sub-array weights[k...(n - 1)]. The code snippet above does this mistake and consequently it gives wrong answer. An easy way to figure that the above code snippet won't work is that: from the problem statement it is clear that the problem has sub-structure based on both knapsack capacity and items array (length). if you observe closely, the way the code is written it does not leverage sub-structure on items array length. It only uses the subs-structure on knapsack capacity.

Tip:

Often times if a problem mentions that you can include an element as many time as you want, or if it specifies that you have infinite number of certain elements, there is a chance that the problem could be solved using Unbounded Knapsack Concept.

Instructor: