[Google Question][LeetCode] Coin Change 2

Problem: You are given coins of different denominations and a total amount of money. Write a method 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:

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

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Input: amount = 10, coins = [10] 
Output: 1

Approach: Let's first think of very basic brute force approach. We can solve this problem using recursion. We can sort the coins array first for some optimization. Here is how the algorithm looks like:

• Sort(coins)
• result = 0
• currAmount = 0
• startIndex = 0
• CALL FindNumOfWays
• DEFINE FindNumOfWays (coins, startIndex, currAmount)
• IF currAmount == amount
• result = result + 1
• RETURN
• FOR i = startIndex to length of coins
• IF currAmount + coins[i] > amount
• break;
• CALL FindNumOfWays(coins, i, currAmount + coins[i])

This will work but it will be really expensive solution and if you see we are solving many sub problems  many times. This tells us we can use dynamic programming here.

We can have a 2D table here where Table[i][j] will tell number of ways to make amount j from coins[0...i]. Obviously Table[length of coins - 1][amount] will be our answer. Let's see how we can fill this table:

• First we sort the coins array.
• Table[i][0] = 1 for i = 0 to length of coins - 1. No matter the number of coins, if amount is 0 then the only way to achieve amount 0 is to leave all the coins so the number of ways will be 1 here.
• Table[0][j] = 1 if j % coins[0] == 0; otherwise 0 for j = 1 to amount.  Remember we have sorted the coins array so coins[0] will have the minimum value. Only way we can make any amount from this minimum value is have multiple same value coins that sum up to the given amount. That means if amount is divisible by coins[0] then we have a way otherwise not.
• FOR i = 1 to coins.Length - 1
• FOR j = 1 to amount
• Table[i][j] = Table[i - 1][j]; // Number of ways when we do not include this coin
• coinAmount = coins[i]
• numOfCoins = 1;
• WHILE (cointAmount * numOfCoins <= j)
• Table[i][j] += Table[i - 1][j - cointAmount * numOfCoins]
• numOfCoins = numOfCoins + 1
• RETURN Table[length of coins - 1][amount]

Now this will work and it is definitely an improvement over the brute force approach but can we still do better.

If you look at the first recursive approach what we were trying to do is we add one coin and then try to find the number of ways recursively for amount - coin_amount. If we think in a way of DP what we can do is maintain a 1D table where Table[i] will tell the number of ways amount 'i' can be achieved using all coins. Looking at the recursive approach, we can say:

Table[currAmount] =  Table[currAmount - coinAmout]

Obviously Table[amount] will be our answer, Here is how we can fill the table:

• Table[0] = 1
• FOR i = 0 to length of coins - 1
• FOR j = coins[i] to amount
• Table[j] += Table[j - coins[i]]
• RETURN Table[amount]

That's all!

Implementation in C#:

    public int Change(int amount, int[] coins) 

    {

        if (amount == 0)

        {

            return 1;

        }

        if (coins?.Length == 0)

        {

            return 0;

        }

        int[] table = new int[amount + 1];

        table[0] = 1;

        foreach (int coin in coins)

        {

            for (int currAmount = coin; currAmount <= amount; ++currAmount)

            {

                table[currAmount] += table[currAmount - coin];

            }

        }

        return table[amount];

    }

Complexity: O(m * n) where m is the number of coins and n amount