Given an integer array coins[] of size "n" representing different denominations of currency and an integer sum.
The task is to find the number of ways you can make sum by using different combinations from coins.
Note: Assume that you have an infinite supply of each type of coin.
Input: sum = 4, coins[] = {1,2,3}
Output: 4
Input: sum = 10, coins[] = {2, 5, 3, 6}
Output: 5
Solutions
Method 1: Memoization
This question is similar to both Number of subsets with a given sum and the Unbounded Knapsack.
The idea is to calculate the total number of ways, once by including the current coins and once by excluding the current coins, and return their sum.
Base Condition: If sum==0, that means one solution has been found, i.e., return 1. Also, if the coins array is exhausted, n==0, there is no way of selecting a coin to make a sum, i.e. return 0.
In recursive solutions of questions where the total number of ways is asked, the base condition usually returns "0" and "1".
If max or min is asked, return max() or min() of options, but if the number of ways or count is asked, add options.
Complexity
The time complexity of this solution is O(2^n) and space complexity is O(n).