518. Coin Change II - Explanation

Description

You are given an integer array coins representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer amount representing a target amount of money.

Return the number of distinct combinations that total up to amount. If it's impossible to make up the amount, return 0.

You may assume that you have an unlimited number of each coin and that each value in coins is unique.

Example 1:

Input: amount = 4, coins = [1,2,3]

Output: 4

Explanation:

1+1+1+1 = 4
1+1+2 = 4
2+2 = 4
1+3 = 4

Example 2:

Input: amount = 7, coins = [2,4]

Output: 0

Constraints:

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

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n * a) time and O(n * a) space, where n is the number of coins and a is the given amount.

Hint 1

As we need to find the total number of combinations, think in terms of recursion and visualize it as a decision tree where multiple coin choices are available at each recursion step. Can you determine a way to allow picking the same coin multiple times? Maybe you should consider the decisions made at each recursion step.

Hint 2

The given coins are unique. We recursively iterate through the coins array using index i, tracking the collected amount along the current path. At each step, we can either skip the current coin or pick it, ensuring the total does not exceed the target. To allow picking the same coin multiple times, we recurse with the same index but an updated amount, generating different combinations.

Hint 3

If we reach the target amount, we return 1. The recursion stops if the index goes out of bounds. We count all possible ways and return the total. This approach is exponential. Can you think of a way to optimize it? Maybe you should consider an approach to avoid redundant computations.

Hint 4

We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a 2D array can be used to store these results.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        coins.sort()

        def dfs(i, a):
            if a == 0:
                return 1
            if i >= len(coins):
                return 0

            res = 0
            if a >= coins[i]:
                res = dfs(i + 1, a)
                res += dfs(i, a - coins[i])
            return res

        return dfs(0, amount)

Time & Space Complexity

Time complexity: $O(2 ^ {max(n, \frac{a}{m})})$
Space complexity: $O(max(n, \frac{a}{m}))$

Where $n$ is the number of coins, $a$ is the given amount and $m$ is the minimum value among all the coins.

2. Dynamic Programming (Top-Down)

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        coins.sort()
        memo = [[-1] * (amount + 1) for _ in range(len(coins) + 1)]

        def dfs(i, a):
            if a == 0:
                return 1
            if i >= len(coins):
                return 0
            if memo[i][a] != -1:
                return memo[i][a]

            res = 0
            if a >= coins[i]:
                res = dfs(i + 1, a)
                res += dfs(i, a - coins[i])

            memo[i][a] = res
            return res

        return dfs(0, amount)

Time & Space Complexity

Time complexity: $O(n * a)$
Space complexity: $O(n * a)$

Where $n$ is the number of coins and $a$ is the given amount.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        coins.sort()
        dp = [[0] * (amount + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            dp[i][0] = 1

        for i in range(n - 1, -1, -1):
            for a in range(amount + 1):
                if a >= coins[i]:
                    dp[i][a] = dp[i + 1][a]
                    dp[i][a] += dp[i][a - coins[i]]

        return dp[0][amount]

Time & Space Complexity

Time complexity: $O(n * a)$
Space complexity: $O(n * a)$

Where $n$ is the number of coins and $a$ is the given amount.

4. Dynamic Programming (Space Optimized)

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

            for a in range(1, amount + 1):
                nextDP[a] = dp[a]
                if a - coins[i] >= 0:
                    nextDP[a] += nextDP[a - coins[i]]
            dp = nextDP
        return dp[amount]

Time & Space Complexity

Time complexity: $O(n * a)$
Space complexity: $O(a)$

Where $n$ is the number of coins and $a$ is the given amount.

5. Dynamic Programming (Optimal)

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for i in range(len(coins) - 1, -1, -1):
            for a in range(1, amount + 1):
                dp[a] += dp[a - coins[i]] if coins[i] <= a else 0
        return dp[amount]

Time & Space Complexity

Time complexity: $O(n * a)$
Space complexity: $O(a)$

Where $n$ is the number of coins and $a$ is the given amount.