Below is the problem:
This problem is similar to the coin change problem. The time complexity and space complexity are also the same. Here, we store the number of combinations instead of the minimum possible coin combination.
We have the same approaches here:
- The brute force approach is where the recursive function make two calls. So the time complexity is 2^amount
- Memoization approach where we define the 2D array where the number of rows = number of coins +1 and number of columns can be the amount+1
- tabulation approach: Here we can optimize to the 1D array with size as the amount+1
