CODEWITHSUNDEEP
c++algorithmrecursion
sparta93
sparta93

Reputation: 3854

Modifying a recursive subsets-sum algorithm

I am using the function given below to recursively check if a subset exists (in a vector) which sums to a given number. However I want to make one modification to it. I print either true or false using the snippet below in my main method.. How can I incorporate that into my check function so that all I do in my main method is just call the function?

     if (check(vec, n, sum) == true)
     cout << "true" << endl;
  else
     cout << "false" << endl;

My function to check whether a subset exists or not.

bool check(vector<int> vec, int sum, int n)
{
   if (sum == 0)
     return true;
   if (n == 0 && sum != 0)
     return false;

   if (vec[n-1] > sum)
    return check(vec, n-1, sum); 

   return check(vec, n-1, sum || check(vec, n-1, sum-vec[n-1]));      
}

Upvotes: 0

Views: 77

Answers (1)

Dante
Dante

Reputation: 404

Just print the return value of check, with std::boolalpha your if else is redundant:

cout << std::boolalpha << check(vec, n, sum) << std::noboolalpha << endl;

Or if you really want to just call the function :

bool check(vector<int> vec, int sum, int n)
{
   if (sum == 0)
   {
     cout << "true" << endl;
     return true;
   }
   if (n == 0 && sum != 0)
   {
     cout << "false" << endl;
     return false;
   }
   if (vec[n-1] > sum)
    return check(vec, n-1, sum); 

   return check(vec, n-1, sum || check(vec, n-1, sum-vec[n-1]));      
}

Upvotes: 1

Related Questions