Coin Change II – LeetCode Solution [Medium]

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.
You may assume that you have an infinite number of each kind of coin.

LeetCode Problem Link

Input

int: amount, int vector: coins[n]

Output

an integer representing the number of combinations that make up that amount

Constraints

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• 0 <= amount <= 5000

Sample Input

coins = [1,2,5], amount = 5

Sample 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

Solution

This problem could be solved in polynomial time using Dynamic programming.

Dynamic Programming

This problem is similar to Coin Change problem, discussed here.

Optimal Substructure (Bottom up approach)

dp[j] represents the number of combinations that make up the amount j

Now according to optimal substructure:
for i = 0 to coins.size()-1:
  for j = coins[i] to amount:
    dp[j] = dp[j] + dp[j-coins[i]]

Base case & Initialisation

dp[0] = 1, number of ways to make sum = 0, is 1 (not including any coin)
dp[j] = 0, if j > 0

Code Implementation

    int change(int amount, vector<int>& coins) {
        int n = (int) coins.size();
        int dp[amount+1];
        dp[0] = 1;
            
        for(int i=1; i<=amount; i++) {
            dp[i] = 0;
        }
            
        for(int i=0; i<n; i++) {
            for (int j=coins[i]; j<=amount; j++) {
                dp[j] += dp[j-coins[i]];
            }
        }

        return dp[amount];
    }

Time complexity of the above solution is O(n*amount) (n is the size of coins vector) and auxiliary space required is O(amount).