Subset Sum Problem using Dynamic Programming

This is a C++ Program that Solves Subset Sum Problem using Dynamic Programming technique.

Problem Description

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.

Problem Solution

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).

Expected Input and Output

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

Program/Source Code

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

```
#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;
```
```
}
```

Program Explanation

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.

Runtime Test Cases

 
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.

« Prev - Boolean Parenthesization Problem using Dynamic Programming

» Next - Minimum Number of Jumps Problem – Dynamic Programming Solutions

Related Posts:

Practice Programming MCQs
Check Programming Books
Practice Computer Science MCQs
Check Computer Science Books
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: