Subset with a given sum and number of subsets

Problem

You are given an array of non-negative integers, you have to find if there’s a subset of this array having sum equal to the given sum. Subset needs not to be contiguous.

Example: 

Input: arr[] = {3, 34, 4, 12, 5, 2}, sum = 8
Output: True  
Subset (3, 5) has sum 8, hence true
Subset with a given sum solution

Naive approach

One way to solve this problem is to generate all the subsets of given array and then find if there’s a subset with given sum. However, time complexity of this method is exponential. This is because there are 2n – 1 (non-empty) subsets of an array of size n.

Dynamic Programming

However, this problem could be solved in polynomial time using Dynamic programming.

Optimal Substructure

DP[i][j] = 1, if there  exists a subset of array arr upto jth element of array with sum i, else 0

Hence,
if (i < A[j-1]) // A[j-1] element > sum (i): (j-1th element excluded) 
  DP[i][j] = DP[i][j-1]
else 
  DP[i][j] = DP[i][j-1] OR DP[i-A[i-1]][j-1]

Code Implementation

//
//  main.cpp
//  Subset with given sum
//
//  Created by Himanshu on 18/09/21.
//

#include <iostream>
using namespace std;
const int N = 7;

int solve (int A[], int sum) {
    int dp[sum+1][N+1];
    
    //subset with sum = 0 can always be
    //formed by an empty subset
    for (int i=0; i<=N; i++) {
        dp[0][i] = 1;
    }
    
    //subset with 0 elements can never
    //form a sum, other than 0
    for (int i=0; i<=sum; i++) {
        dp[i][0] = 0;
    }
    
    for (int i=1; i<=sum; i++) {
        for (int j=1; j<=N; j++) {
            dp[i][j] = dp[i][j-1];
            if (i >= A[j-1]) {
                dp[i][j] = dp[i][j] || dp[i-A[j-1]][j-1];
            }
        }
    }
    
    return dp[sum][N];
    
}
 
int main() {
    int A[N] = {5, 3, 4, 6, 8, 11, 20};
    int sum = 15;
    if (solve(A, sum) != 0) {
        cout<<"Subset with sum "<<sum<<" is present"<<endl;
    } else {
        cout<<"No subset with given sum "<<sum<<" is present"<<endl;
    }
    
    sum = 60;
    if (solve(A, sum) != 0) {
        cout<<"Subset with sum "<<sum<<" is present"<<endl;
    } else {
        cout<<"No subset with given sum "<<sum<<" is present"<<endl;
    }
}

Output:

Subset with sum 15 is present
No subset with given sum 60 is present

Time complexity of above solution is O(sum*N) and auxiliary space required is also O(sum*N).

Here’s a working example: Subset with a given sum

Modified Problem

You are given an array of non-negative integers, you have to find the number of subsets having sum equal to the given sum. Subset needs not to be contiguous.
Note: You should try finding the optimal substructure for this modified problem yourself, if you’ve understood the former problem.

Example: 

Input: arr[] = {5, 3, 4, 6, 8, 11, 20}, sum = 15
Output: 3  
Subset (5, 4, 6), (3, 4, 8), (4, 11) has sum 15, hence 3

Optimal Substructure

DP[i][j] is the number of subsets with sum i of array arr upto jth element of array
Hence, 
// A[j-1] element greater than sum 
if (i < A[j-1])
  DP[i][j] = DP[i][j-1]
else 
  DP[i][j] = DP[i][j-1] + DP[i-A[i-1]][j-1]

Code Implementation

//
//  main.cpp
//  Subset with given sum
//
//  Created by Himanshu on 18/09/21.
//

#include <iostream>
using namespace std;
const int N = 7;

int solve (int A[], int sum) {
    int dp[sum+1][N+1];
    
    for (int i=1; i<=sum; i++) {
        for (int j=1; j<=N; j++) {
            dp[i][j] = 0;
        }
    }
    
    dp[0][0] = 1;

    //subset with sum = 0 can always be
    //formed by an empty subset
    for (int i=1; i<=N; i++) {
        dp[0][i] = 1;
    }
    
    //subset with 0 elements can never
    //form a sum, other than 0
    for (int i=1; i<=sum; i++) {
        dp[i][0] = 0;
    }
    
    for (int i=1; i<=sum; i++) {
        for (int j=1; j<=N; j++) {
            dp[i][j] = dp[i][j-1];
            if (A[j-1] <= i) {
                dp[i][j] = dp[i][j] + dp[i-A[j-1]][j-1];
            }
        }
    }
    
    return dp[sum][N];
    
}
 
int main() {
    int A[N] = {5, 3, 4, 6, 8, 11, 20};
    int sum = 15;
    
    cout<<"Number of subsets with sum "<<sum<<": "<<solve(A, sum)<<endl;
    
    sum = 57;
    cout<<"Number of subsets with sum: "<<sum<<": "<<solve(A, sum)<<endl;
}

Output:

Number of subsets with sum 15: 3
Number of subsets with sum: 57: 1

Time complexity of above solution is O(sum*N) and auxiliary space required is also O(sum*N).

Here’s a working example: Number of subsets with given sum

Leave a Reply

Your email address will not be published. Required fields are marked *