Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 30 minutes | Coding time: 10 minutes
In this article, we will solve Subset Sum problem using a dynamic programming approach which will take O(N * sum) time complexity which is significantly faster than the other approaches which take exponential time.
Subset sum problem is that given a subset A of n positive integers and a value sum is given, find whether or not there exists any subset of the given set, the sum of whose elements is equal to the given value of sum.
Example:
Given the following set of positive numbers:
{ 2, 9, 10, 1, 99, 3}
We need to find if there is a subset for a given sum say 4:
{ 1, 3 }
For another value say 5, there is another subset:
{ 2, 3}
Similarly, for 6, we have {2, 1, 3} as the subset.
For 7, there is no subset where the sum of elements equal to 7.
This problem can be solved using following algorithms:
- Recursive method
- Backtracking
- Dynamic Programing
In this article, we will solve this using Dynamic Programming.
Dynamic Programming
We create a boolean subset[][] and fill it in bottom up manner.
subset[i][j] denotes if there is a subset of sum j with element at index i-1 as the last element
subset[i][j] = true if there is a subset with:
* the i-th element as the last element
* sum equal to j
Base cases include:
j=0 then subset[i][0] will be true as the sum for empty set is 0
If i=0, then subset[0][j] will be false, as with no elements, we can get no sum.
subset[i][0] = true as sum of {} = 0
subset[0][j] = false as with no elements we can get no sum
If element at index i (E1) is greater than j, then subset[i][j] = false as we cannot get a subset of positive numbers with E1 as a member.
If we include element at index i (E1), we get
subset[i][j] = subset[i-1][j-E1];
where E1 = array[i-1]
As if element E1 is included, then we need to find a subset with the first i-1 elements such that the sum is j - E1.
At this point, we should have the value of subset[i-1][j-E1] and hence, we compute it instantly.
Dynamic Programming computes [i][j], for each 1 <= i <= n and 1 <= j <= sum, which is true if subset with sum j can be found using items up to first i items.
It uses value of smaller values i and j already computed. It has the same asymptotic run-time as Memoization but no recursion overhead.
Steps:
1.We create a boolean subset[][] and fill it in bottom up manner.
2.The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i., otherwise false.
3.Finally, we return subset[n][sum]
Complexity
Dynamic Programming
- Worst case time complexity:
Θ(n*sum) - Space complexity:
Θ(sum)
Implementation
Following is the implementation of the Dynamic Programming approach in C++:
/* Part of Cosmos by OpenGenus Foundation */
#include<iostream>
using namespace std;
/*
*Find whether or not there exists any subset
* of array that sum up to targetSum
*/
class Subset_Sum
{
public:
// DYNAMIC PROGRAMMING
bool subsetsum_DP(int a[],int n, int sum)
{
//boolean matrix to store results
bool dp[n+1][sum+1];
//dp[i][j]=whethere there is a subset of sum j in subarray //a[0....i-1]
int i,j;
//initialization
//for sum=0, there is always a subset possible ie., the empty set
for(i=0;i<=n;i++)
dp[i][0]=true;
//if there are no elements in the array, no subset is possible //for a non-zero sum
for(j=1;j<=sum;j++)
dp[0][j]=false;
//i represents the no. of elements of array considered
for(i=1;i<=n;i++)
{
//j represents the sum of subset being searched for
for(j=1;j<=sum;j++)
{
//if using i-1 elements, there is a subset of desired sum
//no need to search further
//the result is true
if(dp[i-1][j]==true)
dp[i][j]=true;
//otherwise, we will inspect
else
{
//if value of current element is greater than the //required sum
//this element cannot be considered
if(a[i-1]>j)
dp[i][j]=false;
//check that after including this element, Is there //any subset present for the remaining sum ie., j-a[i-1]
else
dp[i][j]=dp[i-1][j-a[i-1]];
}
}
}
return dp[n][sum];
}
};
int main()
{
int i, n, sum;
Subset_Sum S;
cout << "Enter the number of elements in the set" << endl;
cin >> n;
int a[n];
cout << "Enter the values" << endl;
for(i=0;i<n;i++)
cin>>a[i];
cout << "Enter the value of sum" << endl;
cin >> sum;
bool f = false;
S.subsetsum_DP(a, n, sum);
if (f)
cout << "subset with the given sum found" << endl;
else
cout << "no required subset found" << endl;
return 0;
}
This performs better than the recursive and backtracking approaches.
