Блог

Я пытаюсь самостоятельно изучить рекурсию. Я выполнил следующее упражнение, которое должно возвращать 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> amp; nums, int targetSum);
bool sumPermute(Vector<int> amp;prefix, Vector<int> amp;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> amp; nums, int targetSum)
{
    Vector<int> prefix;
    return sumPermute(prefix, nums, targetSum);
}

bool sumPermute(Vector<int> amp;prefix, Vector<int> amp;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;
}
  

Заранее благодарю вас.

Я не запускал код, но, похоже, может возникнуть проблема с тем, как true результат от sumPermute (на некотором уровне рекурсии) не будет распространяться уровнем «выше» обратно в источник.

Чтобы исправить это, вам нужно будет проверить возвращаемое значение sumPermute и, если true , убедиться, что оно немедленно передается обратно.

Попробуйте изменить это:

 sumPermute(newPrefix, newRest, target);
  

к этому:

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

Обновление: я проверил эту гипотезу на IDEone, и действительно, именно в этом заключается проблема.

Вам не нужно использовать оператор if. Просто верните рекурсивный вызов:

 return sumPermute(newPrefix, newRest, tartget);
  

Проблема заключалась в том, что вы не возвращали логическое значение обратно через стек.