c++ - boolean 类型的递归

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

更新:我tested this hypothesis on IDEone ，这确实是问题所在。