Sunday 1 December 2013

SubSet Sum Problem Including Negative Integers

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;

}