Coin Change

🙏
জয় শ্রী রাম
🕉

Algorithms and Data Structures: TheAlgorist.com
System Design: DistributedComputing.dev
Low Level Design: LowLevelDesign.io
Frontend Engineering: FrontendEngineering.io

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:

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:

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:

Abhishek Dey

Senior SDE | Chief Architect

Microsoft | University of Florida

View LinkedIn profile

If you have any feedback, please use this form: https://thealgorists.com/Feedback.