#include<iostream>
using namespace std;
bool Subset(int set[],int n,int sum)
{
//Base Case
if(sum==0)
{
return true;
}
else if(n==0 && sum!=0)
{
return false;
}
else if(set[n-1]>sum)
{ //when the element is greater than Sum
return Subset(set,n-1,sum);
}
else
{
return Subset(set,n-1,sum) || Subset(set,n-1,sum-set[n-1]);
}
}
//Driver Program
int main()
{
int set[]={3,34,4,12,5,2};
int sum=9;
int n=sizeof(set)/sizeof(set[0]);
if(Subset(set,n,sum)==true)
{
cout<<"Sub set is found..!"<<endl;
}
else
{
cout<<"Opps..! subset is not found..!!"<<endl;
}
return 0;
}