LeetCode ＃518 Coin Change 2

Posted on | Post modified | In , , , , , , , , ,

Problem

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.

Examples

1
2
3
4
5
6
7
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
1
2
3
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
1
2
Input: amount = 10, coins = [10] 
Output: 1

Note

  • 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

Solution1

Method: Recursive

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        if amount == 0:
            return 1

        return self.helper(coins, len(coins), amount)
        
    def helper(self, coins, idx, amount):
        if idx < 1:
            return 0
        if amount < 0:
            return 0
        if amount == 0:
            return 1

        return self.helper(coins, idx - 1, amount) + self.helper(coins, idx, amount- coins[idx - 1])

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def change(self, amount, coins, idx = float('-inf')):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        if idx == float('-inf'):
            idx = len(coins)
        if amount == 0:
            return 1
        if idx < 1 or amount < 0:
            return 0

        return self.change(amount - coins[idx - 1], coins, idx) + self.change(amount, coins, idx - 1)

Solution2

Method: Dynamic Programming

Time Complexity: O(mn)

Space Complexity: O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        if not coins:
            if amount == 0:
                return 1
            else:
                return 0

        table = [[0 for _ in coins] for _ in range(amount + 1)]
        
        for idx, _ in enumerate(coins):
            table[0][idx] = 1
        
        for idx in range(1, amount + 1):
            for coin_idx, coin_val in enumerate(coins):
                x = table[idx - coin_val][coin_idx] if idx - coin_val >= 0 else 0
                y = table[idx][coin_idx - 1] if coin_idx >= 1 else 0

                table[idx][coin_idx] = x + y
        
        return table[amount][len(coins) - 1]

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        if not coins:
            if amount == 0:
                return 1
            else:
                return 0

        table = [0 for k in range(amount + 1)] 
        table[0] = 1
        for i, val in enumerate(coins): 
            for j in range(val,amount + 1): 
                table[j] += table[j-val] 

        return table[amount]

Reference

https://www.geeksforgeeks.org/coin-change-dp-7/