13.Coin Change 2

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: (Recursion)

Approach: Every step you can have n(no of coins) choices 1) Solutions that do not contain mth coin (or Sm). 2) Solutions that contain at least one Sm.

class Solution
{
public:
    int count = 0;
    void numWays(vector<int> &coins, int sum, int pos)
    {

        if (sum == 0)
        {
            count++;
            return;
        }

        if (sum < 0)
        {
            return;
        }

        if (pos >= coins.size())
        {
            return;
        }

        numWays(coins, sum - coins[pos], pos);
        numWays(coins, sum, pos + 1);
        return;
    }

    int change(int amount, vector<int> &coins)
    {
        numWays(coins, amount, 0);
        return count;
    }
};

Time Complexity: O( No of coins(min value coin) ^ Max Levels(Amount) )

Solution: (DP)

class Solution
{
public:
    int change(int amount, vector<int> &coins)
    {

        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));

        for (int i = 0; i <= n; i++)
        {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= n; i++)
        {

            for (int j = 1; j <= amount; j++)
            {
                if (coins[i - 1] <= j)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
                
            }
        }

        return dp[n][amount];
    }
};

Time Complexity: O(n(no of coins) * amount) Space Complexity: O(n * amount)

Solution: (Optimized Dp )

class Solution
{
public:
    int change(int amount, vector<int> &coins)
    {

        vector<int> dp(amount + 1, 0);
        dp[0] = 1;

        for (int i = 0; i < coins.size(); i++)
        {
            for (int j = 1; j <= amount; j++)
            {
                if (coins[i] <= j)
                {
                    dp[j] = dp[j] + dp[j - coins[i]];
                }
                else
                {
                    dp[j] = dp[j];
                }
            }
        }

        return dp[amount];
    }
};

Time Complexity: O(n(no of coins) * amount) Space Complexity: O(amount)