# Subset sum problem using Dynamic Programming | faceprep

Subset sum problem using Dynamic Programming is discussed here. Given an array and a value, find if there is a subset of the given set with the sum equal to the given sum.

For example,

Sample Input:

10 (Number of elements of the array)
100 (Sum value)
18 23 17 29 1 6 7 30 7 6 (Array elements)

Sample Output:

Yes

Explanation:

18 + 23 + 17 + 29 + 6 + 7  =  100

## Algorithm for subset sum problem

• Create a boolean 2D array table[][] and fill it in a bottom-up manner.
• The value of table[i][j] will be true if there is a subset of the set[0..j-1] with the given sum equal to i., otherwise false.
• Finally, we return table[sum][n]

Program for the subset sum problem using dynamic programming is given below.

#include<iostream>
using namespace std;
int main()
{
int n,sum;
cin>>n>>sum;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int table[n+1][sum+1];
for(int i=0;i<sum+1;i++)
table[0][i]=false;
for(int i=0;i<n+1;i++)
table[i][0]=true;
for(int i=1;i<n+1;i++)
{
for(int j=1;j<sum+1;j++)
{
if(j<a[i-1])
table[i][j]=table[i-1][j];
else
table[i][j]=table[i-1][j]||table[i-1][j-a[i-1]];
}
}
if(table[n][sum])
cout<<“Yes”;
else
cout<<“No”;
}

Test Case 1

I/P
5 15
2 3 4 5 1
O/P
Yes

Test Case 2

I/P
10 20
18 23 17 29 1 6 7 30 7 6
O/P
Yes

Test Case 3

I/P
10 100
18 23 17 29 1 6 7 30 7 6
O/P
Yes

Test Case 4

I/P
10 28
18 23 17 29 1 6 7 30 7 6
O/P
No

Test Case 5

I/P
10 78
18 23 17 29 1 6 7 30 7 6
O/P
Yes