Count Number of subsets with given Sum

Sneha Mallik
Last Updated: May 27, 2022
Difficulty Level :
MEDIUM

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(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).

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(2N). 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(2N).

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) 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

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!

Was this article helpful ?
4 upvotes

Comments

No comments yet

Be the first to share what you think