**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 = 8Output: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 **2 ^{n} – 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 = 15Output: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

## One thought on “Subset with a given sum and number of subsets”