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