0

我正在概括另一个有类似递归调用的问题。就我而言，所使用的变量是字符串，所以我不能简单地通过值来避免循环中递归调用之前和之后的代码。有没有办法把它变成一个迭代循环？请假设循环中递归调用之前和之后的代码无法更改以使此特定实例工作。

此代码测试以查看 nums 中的任何整数组合的总和是否为零。index 的原始值为 0，max 是我想在任何给定解决方案中加起来的最大数字数。

为了进一步澄清，数字可以重复，所以我不能尝试所有可能的组合，因为有无限多。

void findSolution(const vector<int>& nums, vector<int>& my_list, int& mySum,
int index, const int max)
{
    if(mySum == 0) {
        /* print my_list and exit(0) */
    }
    if(index < max) {
        for(int i = 0; i < nums.size(); ++i) {
            my_list.push_back(nums[i]);
            mySum += nums[i];
            findSolution(nums, my_list, mySum, index+1, max);
            mySum -= nums[i];
            my_list.pop_back();
        }
    }
}
4

1 回答 1

0

维护手动堆栈。

在您的情况下，递归调用的唯一独立状态是 I 的值和 index 的值。索引只是递归调用深度。

创建一个称为您的堆栈的 int 标准向量，将其保留为最大值。用 while stack true 替换循环。

在进入循环之前，将零压入堆栈。

将循环中的鳕鱼分成 3 部分。AB 和 C。A 在递归调用之前，B 是你递归调用的，C 在之后。C 中包含循环顶部的增量，它发生在原始代码中的 C 之后。

您在循环中做的第一件事是检查堆栈的顶部是否为 nums 大小或更大。如果是，则弹出堆栈，然后执行 C 并继续，除非堆栈为空，在这种情况下中断。

然后执行A。然后将0压入堆栈，如果堆栈大小小于max，则继续。然后执行 C。您可以使用标志变量删除 C 代码重复。

请记住，堆栈的顶部替换了对 I 的任何引用。基本上我们正在替换一个递归调用，它通过手动维护相同的堆栈自动为我们创建一个堆栈，但只存储我们可以摆脱的绝对最少的数量。循环的开始作为递归调用的结束和循环的开始具有双重职责，因此我们可以取消 goto。

试一试，看完再担心解释。代码到位后，关于标志变量的内容更有意义。

于 2012-12-16T12:25:42.200 回答