Coin Change II
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: 4Explanation:
- 1+1+1+1 = 4
- 1+1+2 = 4
- 2+2 = 4
- 1+3 = 4
Example 2:
Input: amount = 7, coins = [2,4]
Output: 0Constraints:
1 <= coins.length <= 1001 <= coins[i] <= 50000 <= 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.