c++ - 修改递归子集求和算法

Question

我正在使用下面给出的函数递归地检查是否存在总和为给定数字的子集(在 vector 中)。但是我想对其进行修改。我在我的 main 方法中使用下面的代码片段打印 true 或 false。我如何将它合并到我的检查函数中，以便我在 main 方法中所做的只是调用函数？

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

检查子集是否存在的函数。

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]));      
}

Answer 1

只需打印 check 的返回值，使用 std::boolalpha 你的 if else 是多余的:

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

或者如果你真的只想调用函数:

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]));      
}