Problem Statement

Give an array coins of n integers representing different coin denominations. Your task is to find the number of distinct combinations that sum up to a specified amount of money. If it's impossible to achieve the exact amount with any combination of coins, return 0. Single coin can be used any number of times. Return your answer with modulo 109+7.

Examples

Example 1:

Input: coins = [2, 4, 10], amount = 10
Output: 4

Explanation: The four combinations are:
10 = 10
10 = 4 + 4 + 2
10 = 4 + 2 + 2 + 2
10 = 2 + 2 + 2 + 2 + 2

Example 2:

Input: coins = [5], amount = 5
Output: 1

Explanation: There is one combination:
5 = 5

Different Approaches

1️⃣ Recursive Approach

As the question is asking for the total number of ways in which the coins can be summed up to give the target. So, recursion can be used to solve this problem.

Steps to form the recursive solution:

• Express the problem in terms of indexes: We are given ‘n’ coins, where 'n' is the size of the array. Their denomination value is given by the array ‘arr’. So clearly one parameter will be ‘ind’, i.e index up to which the array items are being considered. There is one more parameter, the given target value 'T' which we want to achieve so that while generating subsequences, we can decide whether we want to include a particular coin or not.
  • So, initially, we need to find f(n-1, T) where T is the initial target given to us in the question. f(n-1, T) gives the total number of ways to form the target T by considering coins from index 0 to index n-1 of the arr array.
• Try out all possible choices at a given index: We need to generate all the subsequences. So, use the pick/non-pick technique. There are two choices:
  • Exclude the current coin from the subsequence: First try to find a subsequence without considering the current index coin. If the current coin is excluded, the target sum will not be affected. So call the recursive function f(ind-1,T) to find the remaining answer.
  • Include the current element in the subsequence: Try to find a subsequence by considering the current icoin. As the coin has been included, the target sum will be updated to T-arr[ind].

Now here is the catch, as there is an unlimited supply of coins, we want to again form a solution with the same coin value. So we will not recursively call for f(ind-1, T-arr[ind]) rather we will stay at that index only and call for f(find, T-arr[ind]) to find the answer.

Note: Consider the current coin only when its denomination value (arr[ind]) is less than or equal to the target T.

f(ind, T){
    notTake = 0 + f(ind-1, T)
    take = 0
    if(arr[ind] <= T)
         take = f(ind, T-arr[ind])
}

• Return the sum of 'take' and 'notTake': As we have to return the total number of ways we can form the target, we will return the sum of 'notTake' and 'take' as our answer.

f(ind, T){
    notTake = 0 + f(ind-1, T)
    take = 0
    if(arr[ind] <= T)
         take = f(ind, T-arr[ind])
    return take + notTake
}

• Base Cases:
  • If ind==0, it means we are at the first item so we have only one coin denomination, therefore the following two cases can arise:
  • When target 'T' is divisible by arr[0]. In such case where the target is divisible by the coin element value, return 1 as we will be able to form the target.
  • T is not divisible by arr[0]. In all other cases, we will not be able to form the target, so we will return 0.

Code:

class Solution {
  public:
  // Define a constant for the modulo operation
   const int MOD = 1e9 + 7;
   
   // Recursive function to count the number of ways to form the target amount
   int countWays(vector<int>& coins, int currentIndex, int remainingAmount) {
      // Base Case 1: If the remaining amount is 0, we have found a valid combination
      if (remainingAmount == 0) {
          return 1;
      }
      // Base Case 2: If we've exhausted all coins or the remaining amount is negative, 
      // no valid combination can be formed
      if (currentIndex >= coins.size() || remainingAmount < 0) {
          return 0;
      }

      // Recursive Case 1: Include the current coin and reduce the remaining amount
      int includeCurrentCoin = countWays(coins, currentIndex, remainingAmount - coins[currentIndex]);
      
      // Recursive Case 2: Exclude the current coin and move to the next coin
      int excludeCurrentCoin = countWays(coins, currentIndex + 1, remainingAmount);

      // Return the total number of ways by summing both cases
      return (includeCurrentCoin + excludeCurrentCoin) % MOD;
   }

   // Public function to initiate the recursive counting process
   int count(vector<int>& coins, int numCoins, int targetAmount) {
        // Start the recursion with the first coin and the full target amount
        return countWays(coins, 0, targetAmount);
   }
};

Complexity Analysis:

• Time Complexity: O(2^N), as there are N coints can each one of them has 2 options.
• Space Complexity: O(N), the depth of the recursion stack can be N at max.

2️⃣ Memoization

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

In order to convert a recursive solution to memoization the following steps will be taken:

• Declare a dp array of size [n][target+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The maximum value 'ind' can attain is (n), where n is the size of array and for 'target' only values between 0 to target. Therefore, we need 2D dp array.
  • The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.
• While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
• Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

Code:

class Solution {
  public:
   // Define a constant for the modulo operation
   const int MOD = 1e9 + 7;

   // Recursive function to count the number of ways to form the target amount
   int countWays(vector<int>& coins, int currentIndex, int remainingAmount) {
      // Base Case 1: If the remaining amount is 0, we have found a valid combination
      if (remainingAmount == 0) {
          return 1;
      }
      // Base Case 2: If we've exhausted all coins or the remaining amount is negative, 
      // no valid combination can be formed
      if (currentIndex >= coins.size() || remainingAmount < 0) {
          return 0;
      }

      // Recursive Case 1: Include the current coin and reduce the remaining amount
      int includeCurrentCoin = countWays(coins, currentIndex, remainingAmount - coins[currentIndex]) % MOD;
      
      // Recursive Case 2: Exclude the current coin and move to the next coin
      int excludeCurrentCoin = countWays(coins, currentIndex + 1, remainingAmount) % MOD;

      // Return the total number of ways by summing both cases and applying modulo
      return (includeCurrentCoin + excludeCurrentCoin) % MOD;
   }

   // Public function to initiate the recursive counting process
   int count(vector<int>& coins, int numCoins, int targetAmount) {
        // Start the recursion with the first coin and the full target amount
        return countWays(coins, 0, targetAmount);
   }
};

Complexity Analysis:

• Time Complexity: O(N*Target), as there are N*Target states therefore at max ‘N*Target’ new problems will be solved.
• Space Complexity: O(N*Target) + O(N), the stack space will be O(N) and a 2D array of size N*T is used.