我正在尝试自学递归。我已经完成了以下练习,它应该返回 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;
}
提前谢谢你。
最佳答案
我没有运行代码,但看起来 sumPermute
的 true
结果可能存在问题(在某些递归级别)由“上面”的级别传播回源。
要解决此问题,您需要测试 sumPermute
的返回值,如果 true
确保它立即传回。
尝试改变这个:
sumPermute(newPrefix, newRest, target);
为此:
if(sumPermute(newPrefix, newRest, target)) {
return true;
}
更新:我tested this hypothesis on IDEone ,这确实是问题所在。
关于c++ - boolean 类型的递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7843764/