ブール型の再帰

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（一部の再帰レベル）の結果が "上記"レベルによってソースに戻されないという問題があるようです。

この問題を解決するには、戻り値がsumPermuteであることをテストし、trueである場合はすぐにそれが戻ってくることを確認する必要があります。 I tested this hypothesis on IDEone、そしてどこに問題がある確かにそれはです：アップデート

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

：これまで

sumPermute(newPrefix, newRest, target); 

：

はこれを変更してみてください。

Answer 2

if文を使用する必要はありません。再帰呼び出しを返すだけです。

return sumPermute(newPrefix, newRest, tartget); 

問題は、ブール値をスタックに戻して戻していないという問題でした。