This is a C++ Program that Solves Subset Sum Problem using Dynamic Programming technique.
There is a subset A of n positive integers and a value sum. 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.
This problem can be solved using Dynamic programming. We will proceed with finding whether there exists any subset of sum 1, then for sum 2 and so on. We will keep storing the values in a matrix to avoid recomputation.
Time complexity of this solution is O(n*Sum).
Case-1:
sum=17 n=4 A[]={2,4,6,9} Required subset exists subset {2,6,9} has the sum 17
Case-2:
sum=17 n=4 A[]={2,4,6,8} No Subset found with required sum
Here is source code of the C++ Program to Solve Subset Sum Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
using namespace std;
bool subset_sum(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 the overall result
return dp[n][sum];
}
int main()
{
int i;
int n;
int sum;
cout<<"Enter the value of sum"<<endl;
cin>>sum;
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];
bool result=subset_sum(a,n,sum);
if(result==true)
cout<<"subset with the given sum found";
else
cout<<"no required subset found";
cout<<endl;
return 0;
}
In the main function, we ask the user to input number of elements in the set and the values of all elements. We pass these values to the function subsetSum as parameter. This function will calculate the expected result and return it. The result will be displayed on the basis of the returned value.
Case-1: $ g++ subset_sum.cpp $ ./a.out Enter the value of sum 17 Enter the number of elements in the set 4 Enter the values 2 4 6 9 subset with the given sum found
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Practice Programming MCQs
- Check Programming Books
- Practice Computer Science MCQs
- Check Computer Science Books
- Practice Design & Analysis of Algorithms MCQ