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;
}
Hey,
ReplyDeleteThis program is wrong:
Can you try with This input :
item = {20,35,7,20,6,50,30};
osum = 90
The answer should be : 50+20+20 = 90
It doesn't work for all cases. your recursion logic is completely wrong.
Can you please let us know how did you come up with this recursion logic?
This recursion has passed several test cases it is absolutely right and i will sooner post the tutorial regarding working of this recursion and if you want to do it without recursion you can check the subset sum problem here http://codingstreak.blogspot.in/2013/11/subset-sum-problem-using-dynamic_20.html i have implemented it by using dynamic programming which is far efficient than this recursion problem but it only takes positive numbers as input.
DeleteHi Saurabh,
ReplyDeleteYour recurssion logic is wrong:
I/P: {20,35,7,20,6,50,30};
osum = 90
result should be : 20+20+50 , but your program says couldn't find any combination.
Kiran, kindly look at the code this program is not returning any combination it is just checking whether the combination exist in the code or not if exist than it simply return "Yes" and i have also run this code with the input provided by you it is returning positively "Yes".
ReplyDelete