0518 - Coin Change 2 (Medium)

Problem Link

https://leetcode.com/problems/coin-change-2

Problem Statement

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.

The answer is guaranteed to fit into a 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

Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All the values of coins are unique.
• 0 <= amount <= 5000

Approach 1: Dynamic Programming

This problem is very similar to 0377 - Combination Sum IV (Medium). The only difference is the order of loops. The reason is that (1, 1, 2) and (2, 1, 1) are considered different in that problem.

We can derive the following transition if $target$ is greater or equal to $nums[i]$ where $dp[i]$ represents the number of combinations that sum up to the $target$.

$$dp(amount)=\sum_{i=0}^{n-1} dp(amount - coins[i])$$

Time Complexity: $O(amount * coins.length)$. For each coin, we are going to loop through all the values from $0$ to $amount$.

Space Complexity: $O(amount)$. We are going to create an array of size $amount$.

C++

Written by @wingkwong

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // let dp[i] be the number of combinations that make up to i
        vector<uint> dp(amount + 1);
        // base case
        dp[0] = 1;
        for(auto c : coins) {
            for(int i = 1; i <= amount; i++) {
                // since we need dp[i - c],
                // we need to make sure i - c is greater or equal to 0
                if(i >= c) {
                    // add the previous result
                    dp[i] += dp[i - c];
                }
            }
        }
        return dp.back();
    }
};

Python

Written by @ColeB2

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # initialize dp for all amounts from 0 to amount.
        dp = [0] * (amount + 1)
        # initialize base case for amount 0.
        dp[0] = 1
        # loop through all the coins
        for coin in coins:
            # loop through all the amounts, starting at coin. This
            # prevents us from having to check if i >= coin.
            for i in range(coin, amount + 1):
                # the number of ways we can make each amount is based
                # of the number of ways we can make the amount at each
                # amount-coin
                dp[i] += dp[i - coin]
        # return final value, dp[-1] would also work.
        return dp[amount]

JavaScript

Written by @radojicic23

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
  let dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (let coin of coins) {
    for (let i = coin; i < amount + 1; i++) {
      dp[i] += dp[i - coin];
    }
  }
  return dp[dp.length - 1];
};