Is it possible?

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro