Count of subsets with sum equal to X

Solution Approach

Approach 1: Recursion

We can solve this problem using recursion. Let's see why. We need to choose the elements we want to insert into the subset for making a subset. So, for each element, we have a choice. Whether to choose the current element for the current subset or not? And, assume if we select the current element, then, for all the further elements, we have to keep in mind that their sum should not be greater than X - (sum of all the chosen elements till now) because we don't want the sum of the subset elements to exceed X. Therefore, if we select the i-th element, we now solve the same problem for elements from i+1 to n, with X = X-a[i]. If we don't select the current element, we now solve the same problem, for elements from i+1 to n, with X = X (the sum will remain the same in this case. Therefore, X doesn't change). 

From all this, we can clearly see that this is a recursive approach, and it is a standard knapsack problem. 

The base cases are, 

• When we have traversed the whole array if the sum required now is 0, this means that X sum has been achieved from the elements are taken until now. So, we have found a subset with sum X, therefore, return 1. If the sum required now is not 0, return 0.

In the recursive function "func," if we are at the ith index, and the required sum is X, the recurrence relation is:

• If we take the current element, the required sum now is X-a[i], thus, the answer for this case is, func(a, i+1, X-a[i]).
• If we don't take the current element, the required sum is still X. Thus, the answer for this case is func(a, i+1, X).
• Thus, the final answer for this state is the sum of func(a, i+1, X-a[i]) and func(a, i+1, X).

Steps of implementation are:

• Input the value of n, vector a, and the required sum X.
• Call the function "func," which calculates the number of subsets with a sum equal to X and print the returned answer.
• In the function ""func"":
  • Write the base case. If i==n, we have traversed the whole array, so check if the required sum is 0 or not. If yes, return 1, else return 0.
  • Otherwise, find the answer of both the cases, i.e., if we take the ith element or not, and add the answers of both the cases.
  • Return the above sum of both the cases.

C++ implementation

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

int func(vector<int>&a, int index, int required_sum){
    int n = a.size();
    /* Base case*/
    
    /* 
       	If i==n, we have traversed the whole array, so, check if 
    	the required sum is 0 or not. If yes, return 1, else return 0.
    */
    
    if(index==n){
        if(required_sum==0){
            return 1;
        }
        else{
            return 0;
        }
    }
    /* 
    	Find the answer of both the cases, i.e., if we take the ith 
    	element or not, and add the answers of both the cases
    */
    
    int option1 = func(a,index+1, required_sum-a[index]); 
   	/* 
    	Case when we take the current element
    */
    
    int option2 = func(a,index+1,required_sum); 
    /* 
    	Case when we don't take the current element
    */
    
    int ans = option1+option2;
    return ans;

}

int main()
{
    // Input the value of n,vector a, and the required sum X.
    
    int n;
    n = 6;
    vector<int>a = {2, 3, 5, 6, 8, 10};
    int X;
    X = 10;
    /* 
    	Call the function "func" which calculates the number of subsets with
    	sum equal to X and print the returned answer
    */
    int ans =  func(a,0,X);
    cout<<ans<<endl;
    return 0;
}

Output

3

Complexities

Time complexity

O(2^n), where n is the size of the input array

Reason: Here, for each index, we have 2 choices. Thus, for each index, the recursive function is called twice. Therefore, the time complexity will be exponential and equal to O(2^n).  One more way to find time complexity is to see the recurrence relation. Here, the recurrence relation is T(N) = 2T(N-1) + O(1) which is simplified to O(2^N).

Space complexity

O(n), where n is the size of the input array

Reason: This approach requires a recursion stack, hence the space complexity is equal to the depth of the stack. In the implementation above, the depth of the recursion stack is equal to n, where n is the size of the input array. So, we can say that the space complexity is O(N).

Approach 2: Using memoization

The above approach has exponential complexity. So, using the same idea, we try to optimize it. 

We can use dynamic programming and do memoization. The only new thing we do here is that we make a dp array, which stores the answer for each index and the corresponding required sum, once calculated so that we don't need to do the same calculation again and again. 

And, for each case, before calculating the answer, we check if the answer of the current case is already calculated or not. If yes, return the already calculated answer; otherwise, go on and calculate the answer. 

Steps of implementation are:

• Input the value of n, vector a, and the required sum X.
• Declare a dp map for storing the answer for each state
• We also define a map called visited, which has the value true if a state's answer is already calculated; otherwise, false.
• Call the function "func," which calculates the number of subsets with a sum equal to X and print the returned answer.
• In the function "func":
  • Write the base case. If i==n, we have traversed the whole array, so check if the required sum is 0 or not. If yes, return 1, else return 0.
  • Check if the answer to the current state is already calculated. If yes, return the already calculated answer, otherwise, go on and calculate the answer for this state.
  • Find the answer of both the cases, i.e., if we take the ith element or not, and add the answers of both the cases.
  • Store the calculated answer for this state in the DP array.
  • Update the visited value of this state to true
  • Return the above answer.

C++ implementation

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

int func(vector<int>&a, int index, int required_sum, map<pair<int,int>,int>&dp, map<pair<int,int>,bool>&visited){
    int n = a.size();
    /* Base case*/
    
    /* 
    	If i==n, we have traversed the whole array, so, check if 
    	the required sum is 0 or not. If yes, return 1, else return 0.
    */
    
    if(index==n){
        if(required_sum==0){
            return 1;
        }
        else{
            return 0;
        }
    }
    /* 
    	Check if the answer of the current state is already calculated.
    	If yes, return the already calculated answer, otherwise go on and
    	calculate the answer for this state.
    */
    
    if(visited[{index,required_sum}]==true){
        return dp[{index,required_sum}];
    }
    /* 
    	Find the answer of both the cases, i.e., if we take the ith 
    	element or not, and add the answers of both the cases
    */
    
    int option1 = func(a,index+1, required_sum-a[index],dp,visited); 
    /* 
    	Case when we take the current element
    */
    
    int option2 = func(a,index+1,required_sum,dp,visited); 
    /* 
    	Case when we don't take the current element
    */
    
    int ans = option1+option2;
    /* 
    	Store the calculated answer for this state in the dp array
    */
    
    dp[{index,required_sum}] = ans;
    /* 
    	update the visited value of this state to true
    */
    
    visited[{index,required_sum}] = true;
    
    /*Return ans*/
    
    return ans;

}

int main()
{
    // Input the value of n,vector a, and the required sum X.
    
    int n;
    n = 6;
    vector<int>a = {2, 3, 5, 6, 8, 10};
    int X;
    X = 10;
    /*
    	 Declare a dp map, for storing the answer for each state
    */
    
    map<pair<int,int>,int>dp;
    /* 
    	We also define a map called visited, which has the value true,
    	if a state's answer is already calculated, otherwise, false.
    */
    
    map<pair<int,int>,bool>visited;
    /* 
    	Call the function "func" which calculates the number of subsets with
    	sum equal to X and print the returned answer
    */
    
    int ans =  func(a,0,X,dp,visited);
    cout<<ans<<endl;
    return 0;
}

Output

3

Complexities

Time complexity

O(n*X), where n is the size of the array and X is the required sum.

Reason: Here, we are calculating the answer of each state once only. And there can be as much as (n*X) states. Thus, the time complexity will be (n*X). 

Space complexity

O(n*X), where n is the size of the array and X is the required sum.

Reason: The two maps used here take O(n*X) space. All the other spaces are constant. Thus, the space complexity is O(n*X).

Approach 3: Using tabulation

One thing to notice is that if the element at the current index is itself greater than the required sum, we don't need to take the current element, as taking it will make the sum larger than the required sum. 

So, if the current element is greater than the required sum, we are not left with two choices but only one choice, i.e., not taking the current element. If not, we have both choices.

Also, we know the recurrence relation is dp[i][required_sum] = dp[i-1][required_sum]+dp[i-1][required_sum-a[i]]. 

The above solution required O(n*X) space. We can reduce it to O(X) because the same recurrence relation can be written as dp[required_sum] = dp[required_sum]-dp[required_sum-a[i]] and it will not change the answer.

The base case in this approach will be:

• dp[0]=1 because the sum 0 can always be achieved by not taking any element. 

Steps of implementation are:

• Input the value of n, vector a, and the required sum X.
• Declare a dp array for storing the answer for each state of X
• Call the function "func," which calculates the number of subsets with a sum equal to X and print the returned answer
• In the function ""func"":
  • Write the base case as dp[0] = 1.
  • for all the other cases, run a for loop through each index of the array, and for each index, run another loop through all the required sum values
  • If the current index number is less than or equal to the required sum, calculate the answer from the recurrence relation
  • Return dp[X].

C++ implementation

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

int func(vector<int>&a, int index, int required_sum, vector<int>&dp){
    int n = a.size();
    /* Base case*/
    
    dp[0] = 1;
    /* 
    	for all the other cases, run a for loop through each index of
    	the array, and for each index, run another loop through all the 
    	required sum values
    */
    
    for(int i=0;i<n;i++){
        for(int j=required_sum;j>=0;j--){
            /* 
            	If the current index number is less than or equal to
            	the required sum, calculate the answer from the recurrence
            	relation
            */
            
            if(a[i]<=j){
                dp[j] = dp[j-a[i]]+dp[j];
            }
        }
    }
    /*
    	 Return dp[X]
    */
    
    return dp[required_sum];
}

int main()
{
    // Input the value of n,vector a, and the required sum X.
    
    int n;
    n = 6;
    vector<int>a = {2, 3, 5, 6, 8, 10};
    int X;
    X = 10;
    /* 
    	Declare a dp array, for storing the answer for each state of X
    */
    
    vector<int>dp(X+1);
    /* 
    	Call the function "func" which calculates the number of subsets with
    	sum equal to X and print the returned answer
    */
    
    int ans =  func(a,0,X,dp);
    cout<<ans<<endl;
    return 0;
}

Output

3

Complexities

Time complexity

O(n*X), where n is the size of the array and X is the required sum.

Reason: The for loops take O(n*X) time, and all the other times taken are constant. Thus, the total time complexity is O(n*X).

Space complexity

O(X), where X is the required sum.

Reason: The created dp array takes only O(X) space, and all the other spaces are constant. Thus, the total space complexity is O(X).

Frequently asked questions

1. What is dynamic programming, and where is it used?
   Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results to be used later when needed easily.
    
2. What are overlapping subproblems?
   A problem has overlapping subproblems if it can be divided into smaller problems that are reused multiple times.
    
3. What is an optimal substructure?
   A problem is said to have an optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.
    
4. Is dynamic programming used in real life?
   Yes! Dynamic programming is heavily used in computer networks, routing, graph problems, computer vision, artificial intelligence, machine learning, etc.

Key Takeaways

In this article, we learned how to find the count of subsets with a sum equal to X. The most efficient solution to this problem was based on the concept of dynamic programming. 

This is one of the very interesting and crucial topics, and problems based on this are asked during various coding contests and placements tests. 

I suggest you solve more problems based on this. These are Minimum Subset Sum Difference, the Best time to buy and sell a stock, Maximum profit, Longest Common prefix, wildcard pattern matching, and rod cutting problem. The constant space solution used in this problem also uses some other very important problems like Decode ways.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!