• Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.

#### 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 = 
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:
Input: amount = 10, coins = 
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:

## Python Code:

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

## Python Code:

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.

#### The above content is written by: 