# 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