布尔类型的递归

Question

我正在尝试自己学习递归。我已经完成了以下练习，该练习应该返回 true 或 false，但由于某种原因它总是返回 false。

请有人告诉我为什么我的代码总是返回 false 以及我需要做什么才能纠正这种情况？

/*The subset sum problem is an important and classic problem in     computer
theory. Given a set of integers and a target number, your goal is to 
find a subset of those numbers that sum to that target number. For 
example, given the numbers {3, 7, 1, 8, -3} and the target sum 4, the 
subset {3, 1} sums to 4. On the other hand, if the target sum were 2, 
the result is false since there is no subset that sums to 2.*/
#include <iostream>
#include "genlib.h"
#include "simpio.h"
#include "vector.h"

bool CanMakeSum(Vector<int> & nums, int targetSum);
bool sumPermute(Vector<int> &prefix, Vector<int> &rest, int target);

int main()
{
    int numbers[5] = {3, 7, 1, 8, -3};
    Vector<int> nums;
    for (int i=0; i<5; i++)
    {
        nums.add(numbers[i]);
    }
    cout << "Introduce target: ";
    int target = GetInteger();
    if (CanMakeSum(nums, target))
        cout << "True" << endl;
    else
        cout << "False" << endl;
    return 0;
}

bool CanMakeSum(Vector<int> & nums, int targetSum)
{
    Vector<int> prefix;
    return sumPermute(prefix, nums, targetSum);
}

bool sumPermute(Vector<int> &prefix, Vector<int> &rest, int target)
{
    for (int i=0; i<rest.size(); i++)
    {
        Vector<int> newPrefix;
        newPrefix = prefix;
        newPrefix.add(rest[i]);
        // Check for target value.
        int sum = 0;
        for (int n=0; n<newPrefix.size(); n++)
        {
            sum += newPrefix[n];
        }
        if (sum == target)
            return true;
        Vector<int> newRest;
        for (int j=0; j<i; j++)
        {
            newRest.add(rest[j]);
        }
        for (int k = i+1; k<rest.size(); k++)
        {
            newRest.add(rest[k]);
        }
        sumPermute(newPrefix, newRest, target);
    }
    return false;
}

先感谢您。

Answer 1

我没有运行代码，但看起来可能存在问题，即 sumPermute 的 true 结果（在某些递归级别）不会被“以上”级别返回源。

要解决此问题，您需要测试 sumPermute 的返回值，如果 true 确保它立即传播回来。

尝试将其更改

sumPermute(newPrefix, newRest, target);

为：

if(sumPermute(newPrefix, newRest, target)) {
    return true;
}

更新：我在 IDEone 上测试了这个假设，确实这就是问题所在。

Answer 2

您不需要使用 if 语句。只需返回递归调用：

return sumPermute(newPrefix, newRest, tartget);

问题是您没有通过堆栈返回布尔值。