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.
Note: You can assume that
- 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
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
Input: amount = 3, coins =  Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.
Input: amount = 10, coins =  Output: 1
Idea: this problem is very similar like Coin Change, the difference is to store the total number of combinations to make up the amount, larger amount (dp[i]) is dependent on the smaller one (dp[i – c]) and coins.
class Solution(object): def change(self, amount, coins): """ :type amount: int :type coins: List[int] :rtype: int beats 93.06% """ coins.sort() dp =  +  * amount for c in coins: for i in range(c, amount+1): if dp[i-c]: dp[i] += dp[i-c] return dp[-1] def change0(self, amount, coins): """ :type amount: int :type coins: List[int] :rtype: int https://leetcode.com/problems/coin-change-2/discuss/99210/python-O(n)-space-dp-solution beats 55.21% """ dp =  * (amount + 1) dp = 1 for i in coins: for j in range(1, amount + 1): if j >= i: dp[j] += dp[j - i] return dp[amount] def change1(self, amount, coins): """ :type amount: int :type coins: List[int] :rtype: int https://leetcode.com/problems/coin-change-2/discuss/99235/Classic-problem-python-clean-DP-O(MN) beats 34.72% """ dp =  +  * amount for c in coins: for i in range(1, amount + 1): if i >= c: dp[i] += dp[i - c] return dp[-1] def change2(self, amount, coins): """ :type amount: int :type coins: List[int] :rtype: int TLE for test case: 500, [3,5,7,8,9,10,11] """ if amount < 0: return 0 if amount == 0: return 1 if coins is None: return 0 if len(coins) == 0: if amount == 0: return 1 else: return 0 coins.sort(reverse=True) if amount < coins[-1]: return 0 res =  self.help_func(coins, amount, 0, res) return res def help_func(self, coins, amount, depth, res): """ :param coins: :param amount: :param depth: :param res_list: :return: use current largest coin as much as possible back tracking to use less largest coin if cannot make the target amount repeat above procedure for each coin from large to small """ coins_len = len(coins) if amount == 0: res += 1 return elif amount < 0: return else: if depth == coins_len: return else: i = depth coin_nums = amount // coins[i] for cur_coin_num in range(coin_nums, -1, -1): cur_amount = amount - coins[i] * cur_coin_num self.help_func(coins, cur_amount, depth + 1, res)
Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles about web and mobile development. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money, BlackFriday.fm to check latest news, ads and sales in BlackFriday shopping season.
Follow me @Yaoli0615 at Twitter to get latest tech updates.