QUESTION
We are given a set of N numbers. Our objective is to find out if it is possible to select some numbers from this set such that their sum exactly equals M. \n\nEg. If we have the numbers {3,5,3,1} and M=8, then the answer is yes because of the subset {3,5}. If M=10, then the answer is no because no subset has sum=10.\n\n.
ANSWER
#include<bits/stdc++.h>
using namespace std;
bool isSubsetSum(int set[], int n, int sum)
{
bool subset[n+1][sum+1];
for (int i = 0; i <= n; i++)
subset[i][0] = true;
for (int i = 1; i <= sum; i++)
subset[0][i] = false;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
if(j<set[i-1])
subset[i][j] = subset[i-1][j];
if (j >= set[i-1])
subset[i][j] = subset[i-1][j] || subset[i - 1][j-set[i-1]];
}
}
return subset[n][sum];
}
int main()
{
int set[15];
int sum,i;
int n;
cin>>n>>sum;
for(i=0;i<n;i++)
scanf("%d",&set[i]);
if(isSubsetSum(set,n,sum)==1)
printf("Yes");
else
printf("No");
return 0;
}