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