Problem Statement

Given an array arr of n integers and an integer K, count the number of subsets of the given array that have a sum equal to K. Return the result modulo 109+7.

Examples

Example 1:

Input: arr = [2, 3, 5, 16, 8, 10], K = 10
Output: 3

Explanation: The subsets whose sum is 10 are [2, 8], [10] and [2, 3, 5]

Example 2:

Input: [1, 2, 3, 4, 5], K = 5
Output: 3

Explanation: The subsets whose sum is 5 are [2, 3], [1, 4] and [5]

Different Approaches

1️⃣ Recursive Approach

The idea is to generate all pssible subsets and whenever a single subsets is found whose sum is equal to the given target, simply count it. As, all the subsets needs to generated, recursion can be used to solve this problem.

Steps to form the recursive solution:

• Express the problem in terms of indexes: The array will have an index but there is one more parameter “target”. So, we can say that initially, we need to find(n-1, target) which means that we are counting the number of subsets in the array from index 0 to n-1, whose sum is equal to the target.
  • So, f(ind, target) will count the number of subsets that exists in the array from index 0 to 'ind', whose sum is equal to target.
• Try out all possible choices at a given index: As all the subsets needs to be generated, we will use the pick/non-pick technique. There will be two choices in each function call:
  • Do not include the current element in the subset: First try to find a subset without considering the current index element. For this, make a recursive call to f(ind-1,target).
  • Include the current element in the subset: Now try to find a subset by considering the current index element as part of subset. As the current element(arr[ind]) is included, the remaining target sum will be target - arr[ind]. Therefore, make a function call of f(ind-1,target-arr[ind]).

Note: Consider the current element in the subset only when the current element is less or equal to the target.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, target){
    not pick = f(ind-1, target)
    pick = 0
    if(target <= arr[ind]){
        pick = f(ind-1, target - arr[ind])
    }
           
}

• Return sum of pick and not pick: As we have to return the total count of subsets with the target sum, we will return the sum of taken and notTaken from our recursive call.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, target){
   not pick = f(ind-1, target)
    pick = 0
    if(target <= arr[ind]){
        pick = f(ind-1, target - arr[ind])
    }
    return pick + not pick  
}

• Base cases: There will be two base cases.
  • First, when target == 0, it means that the subset is already found from the previous steps, so simply return 1.
  • Another, when ind==0, it means we are at the first element, so return arr[ind]==target. If the element is equal to the target it will return 1 else 0.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
    const int MOD = 1e9 + 7;  // Define the modulo constant to prevent overflow

private:
    // Helper function to count the number of subsets with the target sum using recursion
    int countSubsets(int currentIndex, int targetSum, vector<int>& arr) {
        // Base Case 1: If the target sum is 0, we've found a valid subset, so return 1
        if (targetSum == 0)
            return 1;

        // Base Case 2: If all elements have been considered and the target sum isn't 0, return 0
        if (currentIndex == 0)
            return (arr[0] == targetSum) ? 1 : 0;

        // Option 1: Exclude the current element and move to the next index
        int excludeCurrent = countSubsets(currentIndex - 1, targetSum, arr);

        // Option 2: Include the current element, but only if it doesn't exceed the target sum
        int includeCurrent = 0;
        if (arr[currentIndex] <= targetSum)
            includeCurrent = countSubsets(currentIndex - 1, targetSum - arr[currentIndex], arr);

        // Return the total count of subsets (with modulo to handle large numbers)
        return (excludeCurrent + includeCurrent) % MOD;
    }

public:
    // Function to find the number of subsets with the given sum K
    int perfectSum(vector<int>& arr, int K) {
        int n = arr.size();  // Get the size of the array

        // Call the recursive function starting from the last index (n-1)
        return countSubsets(n - 1, K, arr);
    }
};

int main() {
    // Example input: array of integers and the target sum K
    vector<int> arr = {1, 2, 2, 3};
    int targetSum = 3;

    // Create an instance of the Solution class
    Solution sol;

    // Call the function and print the result
    cout << "The number of subsets with sum " << targetSum << " is: " << sol.perfectSum(arr, targetSum) << endl;

    return 0;
}

Explanation:

• Recursive Function (countSubsets):
  • This function tries to count how many ways we can form subsets from the array arr such that the sum of the subset is equal to the target sum (targetSum).
  • It works recursively by exploring two possibilities for each element: including it or excluding it.
  • Base Case 1: If the targetSum becomes 0, it means we've found a valid subset, so we return 1.
  • Base Case 2: If the currentIndex goes below 0 and the targetSum isn't 0, it means we've exhausted all elements without finding a valid subset, so we return 0.

Complexity Analysis:

• Time Complexity: O(2^n), where n is the number of elements in the array.
  • As we have two choices:
    • Include the element in the subset.
    • Exclude the elements from the subset.
    • For each element there are 2 choices. Since there are n elements in the array, the total number of different subsets is 2^n. This means in the worst case, the recursive function explores all possible subsets, which results in 2^n recursive calls.
• Space Complexity: O(n)
  • Due to the recursion stack, where n is the length of the array.

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 encountered 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:

#include <bits/stdc++.h>
using namespace std;

class Solution{
public:
    // Modulo to avoid overflow
    int modulo = 1e9 + 7;

    // Recursive function with memoization to count subsets with sum equal to target
    int recursive(vector<int>& arr, int index, int target, vector<vector<int>>& dp) {
        // Base Case 1: If the target sum is 0, we found a valid subset (empty subset also counts)
        if(target == 0) {
            return 1;
        }

        // Base Case 2: If all elements have been considered (index >= arr.size())
        if(index >= arr.size()) {
            return 0;
        }

        // Base Case 3: If target goes below 0, return 0 as no valid subset exists
        if(target < 0) {
            return 0;
        }

        // If the result for this subproblem is already computed, return the stored value
        if(dp[index][target] != -1) {
            return dp[index][target];
        }

        // Option 1: Include the current element in the subset and reduce the target
        int include = recursive(arr, index + 1, target - arr[index], dp);

        // Option 2: Exclude the current element from the subset and keep the target
        int exclude = recursive(arr, index + 1, target, dp);

        // Store the result in the dp table and return it, applying modulo to avoid overflow
        dp[index][target] = (include + exclude) % modulo;
        return dp[index][target];
    }

    // Function to count the number of subsets with sum equal to K
    int perfectSum(vector<int>& arr, int K) {
        int n = arr.size();
        
        // Create a dp table of size (arr.size()) x (K + 1), initialized to -1
        vector<vector<int>> dp(n, vector<int>(K + 1, -1));

        // Call the recursive function starting from the first index
        return recursive(arr, 0, K, dp);
    }
};

int main() {
    vector<int> arr = {12,11,4,9,14,3,20,18,5,8,15,9,12,7,8,15,18,14,13,2,4,5,3,11,10,18,4,4,4,19,2,3,20,5,16,10,6,4,4,14,20,1,16,9,15,19,10,2,18,14};
    int k = 95;  // Target sum

    // Create an instance of the Solution class
    Solution sol;

    // Call the function and print the result
    cout << "The number of subsets with sum " << k << " is: " << sol.perfectSum(arr, k) << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n*K), where n is the number of elements in the array arr, K is the target sum.
  • Recursive Calls: Each subproblem corresponds
• Space Complexity:
  • The maximum depth of the recursive calls will be O(n). Because int he worst case, we recurse down the entire length of the array.