Count Number of subsets with given Sum
Introduction
We are given an array of size ‘N’ and an integer ‘X’ where we have to find the number of subsets with the sum equal to ‘X’.
Counting the number of subsets with a given sum is a variation of the ‘0/1 knapsack’ and the ‘subset sum’ problem. It can be solved using dynamic programming methods.
We know that we have two choices in the 0/1 knapsack problem:
- We can include the item in the subset and do a recursive call for the remaining items
- We can exclude the item from the subset, and we do a recursive call for the remaining items.
After following the steps of the 0/1 knapsack problem, we need to return the count of the subsets having the specified sum.
Credits: GIPHY
Counting the number of subsets is a tedious task that can be achieved easily using dynamic programming. Let us move ahead to understand how its algorithm works.
Algorithm for counting the number of subsets
Recursive Approach
Let us consider an array (also see Data Structures), ‘A’ = [1, 2, 1], ‘X’ = 3 where ‘X’ is the sum value.
The recursion diagram for the array will be:
[1, 2, 1] Sum = 3 / \ (with 1) / \ (without 1) / \ [2, 1] [2, 1] Sum = 2 Sum = 3 / \ / \ / \ / \ [1] [1] [1] [1] Sum=0 Sum=2 Sum=1 Sum=3 / \ / \ / \ / \ [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] Sum: -1 0 1 2 0 1 2 3 |
Now, whenever we get the ‘sum’ as 0, we will increase the ‘count’ variable by 1. Therefore, after this recursive process, we will get ‘count’ = 2., which will include the subsets [1, 2] and [2, 1] having sum value as 3.
ALGORITHM
We will be checking the array recursively to check all the subsets making the sum equal to the given sum. Here, we will be incrementing the variable ‘Count’; otherwise, we will continue to check the next element.
We will be taking an array for which the subsets having ‘Sum’ = ‘X’ is to be found, where ‘X’ is the given sum in the problem.
int subset(int *A, int N, int W){
/*
To check the capacity of the knapsack, if it is complete, then
return 1 as there is no space left. It means that we have found a
subset that equals the given sum 'X'.
*/
if(W == 0){
return 1;
}
/*
If there are no items left and the knapsack is still not complete,
then we return 0 here.
*/
if(N == 0){
return 0;
}
/*
If the space left in the knapsack is less than the element at
A[N - 1] then we return back to the previous element.
*/
if(A[N - 1] > W){
return subset(A, N - 1, W);
}
/*
i (element of the array)
(include i) / \ (not include i)
('A' no. of subsets) A B ('B' no. of subsets)
If we are having an element 'i' and if we include it, then we
get 'A' number of subsets having sum 'X', and if we exclude 'i', we
get 'B' number of subsets having sum 'X'.
The '+' operator is for adding (A + B) number of subsets to count
the total numbers of subsets giving the sum 'X'.
*/
else{
return subset(A, N - 1, W) + subset(A, N - 1, W - A[N - 1]);
}
}
Implementation in C++
// Counting the number of subsets with given sum in 'Recursive Approach'
#include <bits/stdc++.h>
using namespace std;
/*
Function for recursion to find the no. of subsets having the given
sum
*/
int findNoOfSubsets(int *A, int N, int i, int sum, int count){
/*
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){
count++;
}
return count;
}
/*
Recursive relation which will have two cases:
i) The element has to be counted either in the subset and if the
element is counted, the remaining sum that is checked after is
('sum' - 'A[i]' where A[i] is the selected element).
ii) The element has to be counted either in the subset and if
the element is not counted, the remaining sum that is checked
after is the total sum).
*/
count = findNoOfSubsets(A, N, i + 1, sum - A[i], count);
count = findNoOfSubsets(A, N, i + 1, sum , count);
return count;
}
// Main Program
int main(){
int A[] = {1, 4, 3, 2};
int N = sizeof(A) / sizeof(int);
int sum = 5;
// To print the output of counting the number of subsets
cout << "Total number of subsets having sum "<< sum << " =
"<<findNoOfSubsets(A, N, 0, sum, 0);
return 0;
}
Implementation in Java
public class A {
static int findNoOfSubsets(int []A, int N, int i, int sum, int count){
if(i == N){
if(sum == 0){
count++;
}
return count;
}
count = findNoOfSubsets(A, N, i + 1, sum - A[i], count);
count = findNoOfSubsets(A, N, i + 1, sum , count);
return count;
}
public static void main(String[] args) {
int A[] = {1, 4, 3, 2};
int N = 4;
int sum = 5;
System.out.println("Total number of subsets having sum "+sum+" = "+ findNoOfSubsets(A, N, 0, sum, 0));
}
}
Implementation in Python
# Counting the number of subsets with given sum in 'Recursive Approach'
# Function for recursion to find the no. of subsets having the given
# sum
def findNoOfSubsets(A, N, i, summ, count):
# Base case for recursion which is stopped at the Nth Step where
# we check all the subsets of the array
if(i == N):
if(summ == 0):
count+=1
return count
# Recursive relation which will have two cases:
# i) The element has to be counted either in the subset and if the
# element is counted, the remaining sum that is checked after is
# ('sum' - 'A[i]' where A[i] is the selected element).
# ii) The element has to be counted either in the subset and if
# the element is not counted, the remaining sum that is checked
# after is the total sum).
count = findNoOfSubsets(A, N, i + 1, summ - A[i], count);
count = findNoOfSubsets(A, N, i + 1, summ , count);
return count
A = [1, 4, 3, 2];
N = len(A)
summ = 5
# To print the output of counting the number of subsets
print("Total number of subsets having sum ",summ,"=",findNoOfSubsets(A, N, 0, summ, 0))
Output:
Total number of subsets having sum 5 = 2
Complexity Analysis
Time Complexity
The recursive approach takes exponential time complexity, i.e., O(2^{N}), 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(2^{N}).
Space Complexity
The space complexity is O(1) as no extra space is taken, and the space is constant here.
Tabulation DP Approach
We will be using this approach for counting the number of subsets only if the elements present in the array are all positive. Here we will be using a 2D array of size (Arr.size() + 1) x (target + 1) with integer type, which will result in O(N x W) complexity where ‘N’ is the number of elements and ‘W’ is the sum value, and this Dynamic Programming approach is efficient than recursive approach as in a recursive way, there is exponential time complexity which will require more time for larger array size.
/*
If the current value of the element is greater than the current
value of sum then we will just copy the previous answer from
previous case, but if the current value of sum is greater than the
'kth' element, then we will check if the previous state has the
('sum' = 'l' and 'l - A[k]' which should fulfill our purpose).
*/
if(A[k] > l)
matrix[k][l] = matrix[k - 1][l];
else
matrix[k][l] = matrix[k - 1][l] + matrix[k - 1][l - A[k]];
The steps to be followed are:
- We will create an array ‘Subset’,i.e., Subset[ ][ ] and have to fill it up in a bottom-up manner.
- The return value of Subset[ i ][ j ] will be true if the subset of the set[ 0 … (j - 1)] is with a sum value equal to ‘i’, or else it will return false.
- Hence, we return the value of Subset[ N ][ sum ].
Implementation in C++
/*
Counting the number of subsets with given sum in 'Tabulation DP
Approach'
*/
#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 matrix
int matrix[N + 1][sum + 1];
// To initialize the first value of the matrix
matrix[0][0] = 1;
for(int k = 1; k <= sum; k++){
matrix[0][k] = 0;
}
for(int k = 1; k <= N; k++){
matrix[k][0] = 1;
}
for(int k = 1; k <= N; k++){
for(int l = 1; l <= sum; l++){
// If element value is greater than the sum value
if(A[k - 1] > l)
matrix[k][l] = matrix[k - 1][l];
else{
matrix[k][l] = matrix[k - 1][l] +
matrix[k - 1][l - A[k - 1]];
}
}
}
return matrix[N][sum];
}
// Main Program
int main(){
int A[] = {1, 4, 3, 2};
int N = sizeof(A) / sizeof(int);
int sum = 5;
// To print the output of counting the number of subsets
cout << "Total number of subsets having sum " << sum << " =
"<< findSubsetSum(A, N, sum);
return 0;
}
Implementation in Python
/*
Counting the number of subsets with given sum in 'Tabulation DP
Approach'
*/
# Function to find the no. of subsets having the given sum
def findSubsetSum (A, N, summ):
# First, we initialize the matrix
matrix = [[1 for i in range(summ+1)] for j in range(N+1)]
for k in range(1,summ+1):
matrix[0][k] = 0
for k in range(1,N+1):
matrix[k][0] = 1
for k in range(1,N+1):
for l in range(1,summ+1):
# If element value is greater than the sum value
if(A[k - 1] > l):
matrix[k][l] = matrix[k - 1][l]
else:
matrix[k][l] = matrix[k - 1][l] + matrix[k - 1][l - A[k - 1]];
return matrix[N][summ]
A = [1,4,3,2]
N = len(A)
summ = 5
print("Total number of subsets having sum ",summ," = ",findSubsetSum(A, N, summ))
Implementation in Java
public class A {
static int findNoOfSubsets(int[] A, int N, int i, int sum, int count) {
// First, we initialize the matrix
int matrix[][] = new int[N + 1][sum + 1];
// To initialize the first value of the matrix
matrix[0][0] = 1;
for (int k = 1; k <= sum; k++) {
matrix[0][k] = 0;
}
for (int k = 1; k <= N; k++) {
matrix[k][0] = 1;
}
for (int k = 1; k <= N; k++) {
for (int l = 1; l <= sum; l++) {
// If element value is greater than the sum value
if (A[k - 1] > l)
matrix[k][l] = matrix[k - 1][l];
else {
matrix[k][l] = matrix[k - 1][l] +
matrix[k - 1][l - A[k - 1]];
}
}
}
return matrix[N][sum];
}
public static void main(String[] args) {
int A[] = {1, 4, 3, 2};
int N = 4;
int sum = 5;
System.out.println("Total number of subsets having sum "+sum+" = "+ findNoOfSubsets(A, N, 0, sum, 0));
}
}
Output:
Total number of subsets having sum 5 = 2
Complexity Analysis
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), whereas the recursive approach takes exponential time complexity, i.e., O(2^{N}). Hence, the DP method is faster in terms of time complexity.
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.
Frequently Asked Questions
Why is the dynamic programming method used for counting the subsets with a given sum?
There are two methods to solve the ‘counting the subsets with given sum’ using the recursive method and DP method, but the DP method is much more efficient and has a better time complexity of O(N x W), which is better than the recursive method having complexity O(2^{N}).
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(2^{N}) as in the recursive knapsack we try out different combinations where each element in the array has two possible choices to take it or not, thus, making it more time taking.
Conclusion
In this blog, we learned about counting the number of subsets with a given sum using recursion and dynamic programming approach, the working of the code, and some basic concepts.
Recommended Problems
- Top Recursion and Backtracking Interview Questions
- Top Number Theory Problems
- Top Dynamic Programming Problems
Try problems related to subsets here on CodeStudio to learn the competitive programming concepts, data structures, and algorithms. Enroll in our Competitive Programming Course for a deeper understanding of DSA. Also check out some of the Interview Experiences, Interview Bundles, and Guided Paths only on CodeStudio.
Credits: GIPHY
Happy Coding!
Comments
No comments yet
Be the first to share what you think