Given a set of integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Solution:-
#include<iostream>
#include<vector>
using namespace std;
int compute(vector<long long>item , int n ,long long sum , long long osum)
{
if(n < 0 )
return sum==osum;
else
{
if(sum == osum)
return 1;
}
return compute(item , n-1 , sum + item[n] ,osum) || compute(item , n-1 , sum , osum);
}
int main()
{
int T = 0 ;
cin>>T;
vector<long long>item;
int ans = 0 ;
int N = 0 ;
long long osum;
for(int t = 0 ; t < T ; t++)
{
cin>>N;
item.clear();
item.resize(N);
for(long long i = 0 ; i < N ; i++)
{
cin>>item[i];
}
cin>>osum;
ans = compute(item ,N - 1, 0 , osum );
if(ans == 1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
Solution:-
#include<iostream>
#include<vector>
using namespace std;
int compute(vector<long long>item , int n ,long long sum , long long osum)
{
if(n < 0 )
return sum==osum;
else
{
if(sum == osum)
return 1;
}
return compute(item , n-1 , sum + item[n] ,osum) || compute(item , n-1 , sum , osum);
}
int main()
{
int T = 0 ;
cin>>T;
vector<long long>item;
int ans = 0 ;
int N = 0 ;
long long osum;
for(int t = 0 ; t < T ; t++)
{
cin>>N;
item.clear();
item.resize(N);
for(long long i = 0 ; i < N ; i++)
{
cin>>item[i];
}
cin>>osum;
ans = compute(item ,N - 1, 0 , osum );
if(ans == 1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}