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.

Note: You can assume that

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

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

Subscribe to see which companies asked this question.

class Solution {
public:
    int change(int amount, vector<int> coins) {
        /* // Recursive.
        if (amount == 0) {
            return 1;
        }
        if (amount < 0 || coins.size() == 0) {
            return 0;
        }
        int denom = coins[0];
        int factor = 0, sol = 0;
        coins.erase(coins.begin());
        
        while (denom * factor <= amount) {
            sol += change(amount - denom * factor, coins);
            factor++;
        }
        return sol;
        */
        // Dynamic.
        int ch[amount + 1][coins.size() + 1];
        
        for (int i = 0; i < coins.size() + 1; i++) {
            ch[0][i] = 1;
        }
        for (int i = 1; i < amount + 1; i++) {
            ch[i][0] = 0;
        }
        
        for (int i = 1; i < amount + 1; i++) {
            for (int j = 1; j < coins.size() + 1; j++) {
                int sol = 0;
                int factor = 0;
                while (factor * coins[j - 1] <= i) {
                    sol += ch[i - factor * coins[j - 1]][j - 1];
                    factor++;
                }
                ch[i][j] = sol;
            }
        }
        return ch[amount][coins.size()];
    }
};

=====================

/******************************************************************************

                              Online C++ Compiler.

               Code, Compile, Run and Debug C++ program online.

Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>

#include <vector>

#include <map>

using namespace std;

int helper(vector<int>& input, int idx, int target,

            map<string, int>& mp) {

    string key = to_string(idx) + ":" + to_string(target);

    if (mp.count(key) != 0) {

        return mp[key];

    }

    if (idx >= input.size()) {

        mp[key] = 0;

        return 0;

    }

    if (target < 0) {

        mp[key] = 0;

        return 0;

    } else if (target == 0) {

        mp[key] = 1;

        return 1;

    }

    

    int a = helper(input, idx, target - input[idx], mp);

    int b = helper(input, idx + 1, target, mp);

    mp[key] = a + b;

    return a + b;

}

int minWays(vector<int>& input, int target) {

    /*

    - recursive & memoization

    map<string, int> mp;

    int ans = helper(input, 0, target, mp);

    return mp["0:" + to_string(target)];

    */

    

    //- dynamic programming

    if (input.size() == 0) {

        return 0;

    }

    vector<int> dp(target + 1, 0);

    dp[0] = 1;

    

    

    /*

    // This will give total permutations.

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

        for (auto value : input) {

            if (i - value >= 0) {

                dp[i] += dp[i - value];

            }

        }

    }

    */

    

    // But what we need is just the combination. So,

    for (auto value: input) {

        for (int i = value; i <= target; i++) {

            dp[i] += dp[i - value];

        }

    }

    return dp[target];

}

int main()

{

    cout<<"Hello World" << endl;

    

    vector<int> input;

    int target;

    // Test case 1:

    input = {1, 2, 5};

    target = 0;

    cout << minWays(input, target) << endl;

    

    // Test case 2:

    input.clear();

    input = {};

    target = 5;

    cout << minWays(input, target) << endl;

    

    // Test case 3:

    input.clear();

    input = {1, 2, 5};

    target = 5;

    cout << minWays(input, target) << endl;

    

    // Test case 4:

    input.clear();

    input = {1, 5, 15};

    target = 125;

    cout << minWays(input, target) << endl;

    

    return 0;

}