我可以停止执行其他递归树分支吗？

Question

我得到了一个整数向量和一个总和，如果该总和可以从该向量中元素的任意组合生成，我需要 return 该组合。如果可能有不止一种这样的组合，我可以 return 任意一种。

例如，

sum = 20, vector = {6,25,8}，我们可以将 8 6 6 打印为 8+6+6 = 20

sum = 10, vector = {4,6,7}, 我们可以将 6 4 打印为 6+4 = 10

sum = 15, vector = {8,4,5}，我们可以将 5 5 5 打印为 5+5+5 = 15

问题：上面的最后两个例子工作正常，但第一个没有。原因是，如果您为第一个示例绘制递归树，那么根据我的代码，您会得到 flag 变量 true 因为在同一父节点下存在多个 targetSum = 0 的基本情况.因此，最后一个示例打印 8 6 6 8 6.

我的问题是，因为我只需要打印加起来等于 targetSum 的任何可能组合，我可以跳过递归树的其他分支吗？基本上，一旦我们遇到 targetSum = 0 的基本情况，我们就会上树并打印出序列 ?那可能吗？（我曾尝试为此目的使用 stackCount，但如果找到总和为 targetSum 的序列，它只会阻止根节点的右侧子节点执行。）如果没有，则请让我知道如何或修改此代码中的内容，以使其正常工作。

#include <iostream>
#include <vector>
#include <map>

using namespace std;

bool howSum(int &targetSum, vector<int> &elementVector, vector<int> &howSumVector, map<int, bool> &memo, int &stackCount) {
    stackCount++;
    if (memo.find(targetSum) != memo.end())
        return memo[targetSum];
    else if (targetSum == 0)
        return true;
    else if (targetSum < 0)
        return false;
    else {
        for (auto i : elementVector) {
            int remainder = targetSum - i;
            bool flag = howSum(remainder, elementVector, howSumVector, memo, stackCount);
            stackCount--;
            if (flag) {
                    howSumVector.push_back(i);
                    memo[targetSum] = true;
            } else if(memo.find(targetSum) == memo.end())
                memo[targetSum] = false;
            if(stackCount == 1 && !howSumVector.empty())
                return true;
        }
        return memo[targetSum];
    }
}

int main() {
    int stackCount = 0;
    int sum = 20; // test cases 20,10,15
    map<int, bool> memo;
    vector<int> elements = {6,25,8}; // test cases {6,25,8},{4,6,7},{8,4,5}
    vector<int> workingBench = {};
    howSum(sum, elements, workingBench, memo, stackCount);
    for (auto i : workingBench)
        cout << i << " ";
}

Answer 1

您需要在找到匹配时结束递归，在本例中是 flag == true.

if (flag) {
    howSumVector.push_back(i);
    memo[targetSum] = true;
    return true; // We found a match! Stop searching!
}

编辑：

您没有正确使用备忘录。由于您只需要一种可能的解决方案，因此无需跟踪某个组合是否有效。

您想要的是跟踪之前是否有相同的余数。如果这样做，您可以直接中止搜索。

如果目标是 20 并且您有一些数字组合可以让您得到 5 的余数，那么是什么数字组合让我们达到目标并不重要。

假设我们无法从 15 到达目标，那么如果我们以某种不同的数字组合再次到达 15，我们已经知道我们永远无法从 15 到达目标，所以我们可以中止搜索那里。

如果我们可以从 15 开始达到目标，我们已经找到了解决方案并且递归已经结束，所以我们也不关心那个结果。

这是一个修改后的完整示例。

#include <iostream>
#include <vector>
#include <set>

using namespace std;

bool howSum(int targetSum, const vector<int> &elementVector, vector<int> &howSumVector, set<int> &memo) {
    if (memo.find(targetSum) != memo.end()) {
        return false;
    }
    memo.insert(targetSum);

    if (targetSum == 0) {
        return true;
    } else if (targetSum < 0) {
        return false;
    } else {
        for (auto i : elementVector) {
            bool flag = howSum(targetSum - i, elementVector, howSumVector, memo);
            if (flag) {
                howSumVector.push_back(i);
                return true;
            }
        }
        return false;
    }
}

int main() {
    int sum = 20; //20,10,15
    set<int> memo;
    vector<int> elements = {6,25,8}; // {6,25,8},{4,6,7},{8,4,5}
    vector<int> workingBench = {};
    howSum(sum, elements, workingBench, memo);
    if (workingBench.empty())
        cout << "not possible";
    else
        for (auto i : workingBench)
            cout << i << " ";
}

其他一些注意事项。我改为按值传递 targetSum 。您永远不会修改它，因此通过引用传递是没有意义的。

我也将 elementVector 更改为由 const & 传递，因为我们不想修改它。这只是一个好习惯。

Answer 2

我的最终代码-

#include <iostream>
#include <vector>
#include <map>

using namespace std;

bool howSum(int &targetSum, vector<int> &elementVector, vector<int> &howSumVector, map<int, bool> &memo) {
    if (memo.find(targetSum) != memo.end())
        return memo[targetSum];
    else if (targetSum == 0)
        return true;
    else if (targetSum < 0)
        return false;
    else {
        for (auto i : elementVector) {
            int remainder = targetSum - i;
            bool flag = howSum(remainder, elementVector, howSumVector, memo);
            if (flag) {
                howSumVector.push_back(i);
                memo[targetSum] = true;
                return true;
            } else if (memo.find(targetSum) == memo.end()) // if targetSum is NOT in memo
                memo[targetSum] = false;
        }
        return false;
    }
}

int main() {
    int sum = 20; //20,10,15
    map<int, bool> memo;
    vector<int> elements = {6,25,8}; // {6,25,8},{4,6,7},{8,4,5}
    vector<int> workingBench = {};
    howSum(sum, elements, workingBench, memo);
    if (workingBench.empty())
        cout << "not possible";
    else
        for (auto i : workingBench)
            cout << i << " ";
}

我可以停止执行其他递归树分支吗？

Can I stop other recursion tree branches from executing?

c++

recursion

dynamic-programming