Saturday 13 August 2016

Check if sum is present in subset of a given array.

#include <iostream>
#define  ll long long int
using namespace std;

int main() {
ll sum,i,req_sum,n,f=0,x;
cin>>n>>req_sum;
ll a[n];
for(i=0;i<n;i++)
cin>>a[i];
x=(1<<n)-1;
for(i=1;i<=x;i++)
{
int b=i;
int j=0;
sum=0;
while(b)
{
int c=b%2;
if(c==1)
{
sum+=a[j];
}
j++;
b=b/2;

}

if(sum==req_sum)
{
f=1;
break;
}

}
if(f==1)
cout<<"Required Sum is Present in Subset of given Set\n";
else
cout<<"Required Sum is not Present in Subset of given Set\n";
// your code goes here
return 0;
}

No comments:

Post a Comment