Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
Approaches for Counting the Number of Subsets
3.1.
Recursive Approach
3.1.1.
Algorithm 
3.1.2.
Dry Run
3.1.3.
Implementation in C++
3.1.4.
Implementation in Java
3.1.5.
Recursive Time Complexity 
3.1.6.
Recursive Space Complexity 
3.2.
Dynamic Programming Approach
3.2.1.
Memoization
3.2.2.
Tabulation
3.2.3.
DP Time Complexity 
3.2.4.
DP Space Complexity 
4.
Frequently Asked Questions
4.1.
Why is the dynamic programming method used for counting the subsets with a given sum?
4.2.
What is the condition for a set A to be a subset of B?
4.3.
How is the dynamic programming method more efficient in time complexity?
4.4.
Will the above approach work if we have negative elements in our array?
4.5.
Will the above approach work for duplicate elements?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count Number of Subsets With Given Sum

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 

Counting the number of subsets with a given sum is a standard Recursion problem that can be optimized using dynamic programming. It is a variation of the 0/1 knapsack and the subset sum problem. We know that dynamic programming can be applied to any problem where the following two properties are being followed

  1. Overlapping Subproblems
  2. Optimal Substructure
     

The given problem follows both the above-mentioned properties and hence can be optimized using dynamic programming.

Count Number of Subsets With Given Sum

In the article, we will first look at the recursive approach which generates all the possible subsets and hence has an exponential time complexity. In the second and the optimized approach, we will use dynamic programming to help us attain polynomial time complexity.

Problem Statement

Given an array ‘A’ of size ‘N’ and an integer ‘X.’ The task is to find the number of subsets with the sum of their elements equal to ‘X.’ 

We have two choices in the 0/1 knapsack problem:

  1. We can include the current item in the subset and make a recursive call for the remaining items.
  2. We can exclude the item from the subset, and do a recursive call for the remaining items.
     

After following the steps of the 0/1 knapsack problem, we return the count of the subsets having the specified sum.

Input

Given array ‘A’= [1,2,1] and ‘X’=3.

Output

The count of subsets is 2.

Explanation

In the above array, we have two subsets with a sum equal to 3. The first one is [1,2], and the second one is [2,1]. Note that two subsets are different if they contain at least one index, which is contained in one but not in the other.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approaches for Counting the Number of Subsets

To count the number of subsets with a given sum, there are two approaches, naive and dynamic programming. The first approach uses Recursion and generates all possible subsets. Then it checks whether a particular subset satisfies the given condition or not.
In the second approach, we optimize the recursive approach using dynamic programming and reduce the logarithmic time complexity to polynomial time complexity.

Recursive Approach

Consider an array, ‘A’ = [1, 2, 1], ‘X’ = 3 where ‘X’ is the sum value. In the recursive approach, we will generate all possible subsets of the given array. At each element, we have two choices, either to take it or not to take it. Every time we take an element, decrement the sum value by that element. Else, keep the sum the same. Now, whenever we get the ‘Sum’ as 0, we will increase the ‘count’ variable by 1. Following this, we get [1, 2] and [2, 1] having a sum value of 3, hence the count equals 2. 

Algorithm 

  1. Generate all the possible subsets from the given array.
     
  2. Initialize a ‘count’ variable equal to zero.
     
  3. For generating the subsets, every element will have two choices, either to be included or to be excluded. Therefore, there will be a total of 2n subsets, where n is the number of elements in the array.
     
  4. If we have reached the end of the array, check if the current sum is 0 or not. If the current sum is zero, we have generated a valid subset, hence incrementing the count variable by 1. 
     
  5. Else, if we are at a valid array index, make two recursive calls. One with the current element included and the other without the current element.
     
  6. Every time an element is included, decrease the sum by the value of the included element. Else, keep the sum as it is. 

Dry Run

For array= [1, 2, 1] and sum = 3.

The size of the array is 3. So we will terminate the process once we reach index=3.

At index=0, we make two recursive calls, one with array[0] included and the other without array[0].

Next, at index=1, we again make two recursive calls, one with arr[1] included and the other without arr[1].  Note that, every time we include the element, decrement the value of the current sum by the value of the included element.

Next, we repeat the same for index=2.

Recursive approach to count the number of subsets with a given sum

Once we have index=size of the array, which is 3, we check if the current sum=0. If yes, then we return 1 else, we return 0. 

In the above recursion tree, we can see that sum=0 occurs two times. Hence the final answer returned =2.

Implementation in C++

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

int findNoOfSubsets(int *A, int N, int i, int sum) {
    /*
        Base case for recursion which is stopped at the Nth Step where
        we check all the subsets of the array
    */
    if (i == N) {
        if (sum == 0)
            return 1;
        else
            return 0;
    }
    
    /*
      Either we will take the current item or we will not
    */
    int take = 0, notTake = 0;
    take = findNoOfSubsets(A, N, i + 1, sum - A[i]);
    notTake = findNoOfSubsets(A, N, i + 1, sum);
    
    // Return the computed value
    return (take + notTake);
}

// Main Program
int main(){
    int A[] = {1, 2, 1};
    int N = sizeof(A) / sizeof(int);
    int sum = 3;
    
    // To print the output of counting the number of subsets
    cout << "Total number of subsets having sum " << sum << " = " << findNoOfSubsets(A, N, 0, sum);
    return 0;
}


Output

Count Number of Subsets With Given Sum

Implementation in Java

import java.util.*;
public class Main {
	static int findNoOfSubsets(int[] A, int N, int i, int sum) {
    	/*
        	Base case for recursion which is stopped at the Nth Step where
        	we check all the subsets of the array
    	*/
    	if (i == N) {
        	if (sum == 0)
            	return 1;
        	else
            	return 0;
    	}
    	
    	/*
      	Either we will take the current item or we will not
    	*/
    	int take = 0, notTake = 0;
    	take = findNoOfSubsets(A, N, i + 1, sum - A[i]);
    	notTake = findNoOfSubsets(A, N, i + 1, sum);
    	
    	// Return the computed value
    	return (take + notTake);
	}
	
	// Main Program
	public static void main(String[] args) {
    	int[] A = {1, 2, 1};
    	int N = A.length;
    	int sum = 3;
    	
    	// To print the output of counting the number of subsets
    	System.out.println("Total number of subsets having sum " + sum + " = " + findNoOfSubsets(A, N, 0, sum));
    }
}


Output

Count Number of Subsets With Given Sum

Recursive Time Complexity 

The recursive approach takes exponential time complexity, i.e., O(2N) since for the ‘N’ number of elements we have two possible choices to either include or exclude it. Hence the time complexity is huge, which is O(2N).

Recursive Space Complexity 

The space complexity is O(1) as no extra space is taken, and the space is constant here.

Dynamic Programming Approach

The given problem can also be solved using dynamic programming approach. It satisfies both the properties required for categorizing a problem as a DP problem, that is, optimal substructure and overlapping subproblems. Let's see how. 

The size of the DP array depends on the parameters of the recursive call, whose values change every time we make a new recursive call.

With close observation, we can clearly see that in every recursive call, the index of the current element and the sum value changes. 

Therefore, dp[x][y] represents the number of subsets with sum=y and array elements from [0… x-1]. 

Lets us consider we are at an element with index ‘x’, and the current sum is ‘y’.  

The number of subsets if we don't consider the current element, will be equal to the number of subsets with sum y, and x-1 elements, that is, dp[x-1][y].

The number of subsets if we consider the current element equals the number of subsets till x-1 elements, and sum y-A[x-1], that is, dp[x-1][y-A[x-1]], where ‘A’ represents the array of elements.  

Thus, dp[x][y]= dp[x-1][y] + dp[x-1][y-A[x-1]].

Let us now implement this approach with memoization and tabulation, which are the two standard techniques of dynamic programming.

Memoization

Memoization is an optimization to recursion problems in which the same result is being calculated multiple times. It is very similar to the basic recursion code, the only difference comes in storing and retrieving the results. The first time we calculate an answer to a subproblem, we store it in a table. The next time the same result is required, instead of calculating it again, we directly retrieve it from the table.

Algorithm

  1. Write the recursive function as the above approach.
     
  2. Create a 2D DP array of size (N+1)*(sum+1) and initialize it with -1.
     
  3. Every time a new recursive call is made, first check if that particular value is already computed and exists in the dp table.
     
  4. If yes, retrieve it from the dp table.
     
  5. Else, calculate the required sum and store it in the dp table for further use.
     

Implementation in C++

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

// Create a 2D dp table
vector<vector<int>> dp;

int findNoOfSubsets(int *A, int N, int i, int sum) {
    /*
        Base case for recursion which is stopped at the Nth Step where
        we check all the subsets of the array
    */
    if (i == N) {
        if (sum == 0)
            return 1;
        else
            return 0;
    }
    
    if(sum<0)
		return 0;
		
    // If the required value is already computed, retrieve it from the dp table.
    if (dp[i][sum] != -1)
        return dp[i][sum];
        
    /*
      Either we will take the current item or we will not
    */
    int take = 0, notTake = 0;
    take = findNoOfSubsets(A, N, i + 1, sum - A[i]);
    notTake = findNoOfSubsets(A, N, i + 1, sum);
    
    // Enter the computed value in the dp table and then return it.
    return dp[i][sum] = (take + notTake);
}

// Main Program
int main(){
    int A[] = {1, 2, 1};
    int N = sizeof(A) / sizeof(int);
    int sum = 3;
    // To print the output of counting the number of subsets
    dp.resize(N + 1, vector<int>(sum + 1, -1));
    cout << "Total number of subsets having sum " << sum << " = " << findNoOfSubsets(A, N, 0, sum);
    return 0;
}


Output

Count Number of Subsets With Given Sum

Implementation in Java

import java.util.*;
public class Main {
    // Create a 2D dp table
	static int[][] dp;
	
	static int findNoOfSubsets(int[] A, int N, int i, int sum) {
    	/*
      	  Base case for recursion which is stopped at the Nth Step where
          we check all the subsets of the array
   		*/
    	if (i == N) {
        	if (sum == 0)
            	return 1;
        	else
            	return 0;
    	}
    	
    	if(sum<0)
			return 0;
			
    	// If the required value is already computed, retrieve it from the dp table.
    	if (dp[i][sum] != -1)
        	return dp[i][sum];
        	
    	/*
    		Either we will take the current item or we will not
    	*/
    	int take = 0, notTake = 0;
   		take = findNoOfSubsets(A, N, i + 1, sum - A[i]);
    	notTake = findNoOfSubsets(A, N, i + 1, sum);

    	// Enter the computed value in the dp table and then return it.
    	return dp[i][sum] = (take + notTake);
	}
	
	// Main Program
	public static void main(String[] args) {
    	int[] A = {1, 2, 1};
    	int N = A.length;
    	int sum = 3;
    	
    	// To print the output of counting the number of subsets
    	dp = new int[N + 1][sum + 1];
    	for (int i = 0; i <= N; i++)
        	Arrays.fill(dp[i], -1);
    	System.out.println("Total number of subsets having sum " + sum + " = " + findNoOfSubsets(A, N, 0, sum));
    }
}


Output

Count Number of Subsets With Given Sum

Tabulation

This method is applicable only in cases where all the elements of the input array are positive. We change the recursive approach into iterative method. But this iterative method might now work correctly if there are 0’s or negative elements in the input array. It works perfectly correct only when our array contains only positive elements.

We create a 2D dp array in the same way as explained above in memoization and fill the values in an iterative manner. The state represented by dp[x][y] is the same as the memoization approach. 

However, the tabulation approach also requires some initialization which is explained in the algorithm below.

Algorithm

  1. Create a 2D integer array of size (size + 1) x (sum + 1).
     
  2. Set dp[0][0]=1 since if we have sum as 0 and number of elements also 0, we can take null subset {}, hence the count is 1.
     
  3. Set dp[0][y] as 0, where ‘y’ ranges from 1 to the value of sum, since if we have zero elements and non-zero sum, there is no possible subset.
     
  4. Now, iterate through the dp table. If A[x-1] is greater than the current sum y, we copy the answer with x-1 elements of the array and sum y, that is, dp[x-1][y].
     
  5. Else, we consider both cases and set dp[x][y] equal to dp[x-1][y]+dp[x-1][y-A[x-1]]. 
     
  6. At last, return dp[N][sum]. 
     

Dry Run

Given, the input array A= [1,2,1] and the target sum X=3.

The 2D integer array ‘dp’ is of size (4*4). Once the initialization is complete after steps 2 and 3 mentioned above, the dp table looks as follows-

Tabulation approach to count the number of subsets with a given sum

Next, follow steps 5 and 6 for every remaining cell and fill the dp table.

For example, for row=1, column=0

A[0]>0 ? Yes

Therefore, dp[1][0]=dp[0][0]

Similarly, we calculate for all the cells using nested loops.

Tabulation approach to count the number of subsets with a given sum

At last, we return dp[3][3] which is the required answer. 

Hence, count of subsets for the given problem is 2.

Implementation in C++

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

// Function to find the no. of subsets having the given sum
int findSubsetSum(int A[], int N, int sum){
    // First, we initialize the dp
    int dp[N + 1][sum + 1];
    
    // To initialize the first value of the dp
    dp[0][0] = 1;
    
    for (int k = 1; k <= sum; k++) {
        dp[0][k] = 0;
    }
    
    for (int k = 1; k <= N; k++) {
        for (int l = 0; l <= sum; l++) {
            // If element value is greater than the sum value
            if (A[k - 1] > l)
                dp[k][l] = dp[k - 1][l];
            else{
                dp[k][l] = dp[k - 1][l] + dp[k - 1][l - A[k - 1]];
            }
        }
    }
    return dp[N][sum];
}

// Main Program
int main(){
    int A[] = {1,2,1};
    int N = sizeof(A) / sizeof(int);
    int sum = 3;
    
    // To print the output of counting the number of subsets
    cout << "Total number of subsets having sum " << sum << " = " << findSubsetSum(A, N, sum);
    return 0;
}


Output

Count Number of Subsets With Given Sum

Implementation in Java

import java.util.*;
public class Main {
    // Function to find the no. of subsets having the given sum
    static int findSubsetSum(int A[], int N, int sum) {
    	// First, we initialise the dp
    	int[][] dp = new int[N + 1][sum + 1];
    	
    	// To initialise the first value of the dp
    	dp[0][0] = 1;
    	
    	for (int k = 1; k <= sum; k++) {
        	dp[0][k] = 0;
    	}
    	
    	for (int k = 1; k <= N; k++) {
        	for (int l = 0; l <= sum; l++) {
            	// If element value is greater than the sum value
            	if (A[k - 1] > l)
                	dp[k][l] = dp[k - 1][l];
            	else {
                	dp[k][l] = dp[k - 1][l] + dp[k - 1][l - A[k - 1]];
            	}
        	}
    	}
    	return dp[N][sum];
	}
	
	// Main Program
	public static void main(String[] args) {
    	int[] A = {1, 2, 1};
    	int N = A.length;
    	int sum = 3;
    	
    	// To print the output of counting the number of subsets
    	System.out.println("Total number of subsets having sum " + sum + " = " +findSubsetSum(A, N, sum));
	}
}


Output

Count Number of Subsets With Given Sum

Note-

If we sort the given input array in descending order, the above tabulation code can be used for every array containing non-negative elements.

DP Time Complexity 

The time complexity of this problem is O(N x W), where ‘N’ is the number of items, and ‘W’ is the targeted sum value in the dynamic programming method. This is the worst-case time complexity as the nested loop has limits from [1 to ‘N’] and [1 to ‘sum’], respectively. The dynamic programming method takes polynomial time complexity, i.e., O(N x W).

DP Space Complexity 

The auxiliary space to be taken is O(N x W) as we take the 2-D array, which takes a space of O(N x W), where ‘N’ is the number of items and ‘W’ is the targeted sum value.

Refer to know about :  Longest common subsequence

Frequently Asked Questions

Why is the dynamic programming method used for counting the subsets with a given sum?

The subset sum problem satisfies both the requirements of categorizing a problem as a Dynamic Programming Problem- optimal substructure and overlapping subproblems. It provides a better time complexity than the recursive solution to solve the same problem. 

What is the condition for a set A to be a subset of B?

If all the items of set A are present in set B, then set A is a subset of set B.

How is the dynamic programming method more efficient in time complexity?

Dynamic programming has a time complexity of O(N x W), whereas in the recursive method, the time complexity is O(2N).

Will the above approach work if we have negative elements in our array?

No, the above approach would fail in that case as there can still exist a possibility of including elements even after achieving a zero as the sum.

Will the above approach work for duplicate elements?

Yes, the above approach would work if an element occurs multiple times in the array. This is because this approach considers the item at each ‘index’ ( and not the element ) as a unique item.

You can also read about - Strong number in c

Conclusion

This article discusses the problem of solving the number of subsets with a given sum using two approaches. The first one is using the naive approach, which implements basic recursion without any optimization. In the second approach, we have used dynamic programming to obtain a better time complexity.  

We hope that this blog made the concepts of this problem crystal clear to you. For more such articles, check out the following links

  1. 0-1 Knapsack
  2. Dynamic programming
  3. Overlapping substructure vs overlapping subproblems
     

Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Coding!

Previous article
Check for Nodes from given two BSTs with a sum equal to X
Next article
Subset Sum Problem
Live masterclass