Coin Change II

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

Intuition

For Coin Change, the question is asking for the minimum coin to make up an amount. As a result, at amount i, we need to know what's the value for amount i - coin in order to +1 to use the current coins. Therefore we have

dp[amount] = dp[amount - coin] + 1

However in this question, we are interested in total amount of all coins. As a result, we need to do

for coin in coins:
    for amount in range(len(dp)):
        dp[amount] += dp[amount - coin]

Implementation

class Solution:
    def change(self, target: int, coins: List[int]) -> int:
        dp = [0 for i in range(target + 1)]
        dp[0] = 1

        for coin in coins:
            for amount in range(len(dp)):
                if coin > amount: continue
                dp[amount] += dp[amount - coin] 

        return dp[-1]

Time complexity: $O(coin \times target)$
Space complexity: $O(target)$