Problem
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
Solution
/**
* @param {number} amount
* @param {number[]} coins
* @return {number}
*/
var change = function(amount, coins) {
coins.sort((a, b) => b - a);
return helper(amount, coins, Array(coins.length + 1).fill(0).map(() => []));
};
var helper = function(amount, coins, dp) {
if (amount === 0) return 1;
if (dp[coins.length][amount] !== undefined) return dp[coins.length][amount];
var res = 0;
for (var i = 0; i < coins.length; i++) {
if (amount >= coins[i]) {
res += helper(amount - coins[i], coins.slice(i), dp);
}
}
dp[coins.length][amount] = res;
return res;
};
Explain:
- sort
coins
array, to avoid duplicate answer f(5, [5,2,1]) = f(0, [5,2,1]) + f(3, [2,1]) + f(4, [1])
f(0, []) = 1
- cache every compute so that we only compute same case once
Complexity:
- Time complexity : O(n * m).
- Space complexity : O(n * m).