Do you think IIT Guwahati certified course can help you in your career?
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
Overlapping Subproblems
Optimal Substructure
The given problem follows both the above-mentioned properties and hence can be optimized using dynamic programming.
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:
We can include the current item in the subset and make a recursive call for the remaining items.
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.
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
Generate all the possible subsets from the given array.
Initialize a ‘count’ variable equal to zero.
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.
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.
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.
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.
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;
}
You can also try this code with Online C++ Compiler
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));
}
}
You can also try this code with Online Java Compiler
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
Write the recursive function as the above approach.
Create a 2D DP array of size (N+1)*(sum+1) and initialize it with -1.
Every time a new recursive call is made, first check if that particular value is already computed and exists in the dp table.
If yes, retrieve it from the dp table.
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;
}
You can also try this code with Online C++ Compiler
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));
}
}
You can also try this code with Online Java Compiler
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
Create a 2D integer array of size (size + 1) x (sum + 1).
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.
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.
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].
Else, we consider both cases and set dp[x][y] equal to dp[x-1][y]+dp[x-1][y-A[x-1]].
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-
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.
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;
}
You can also try this code with Online C++ Compiler
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));
}
}
You can also try this code with Online Java Compiler
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.
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.
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
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 problems, interview experiences, and interview bundles for placement preparations.
However, you may consider our paid courses to give your career an edge over others!
86+ registered 