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