c++ - 递归求和任务的错误答案

我正在研究一个问题，使用递归方法打印所有等于给定数字n的非递增子序列。我知道我的递归算法有问题，但是我已经多次遍历了该过程，但找不到错误。输入4，我的代码给出输出:

4
431
4322
432211
43213
4321321
43213212
4321321211
我相信递归可以保留以前的数字或过去递归调用中使用的总和，但是找不到原因。有人可以帮我弄清楚为什么程序没有给出正确的输出吗？

#include <iostream>
#include <string>

using namespace std;

int n;

void sums(int sum, string str)
{
  if (sum==n)
  {
    cout << str << "\n";
    return;
  }
  for (int i = n-sum; i >= 1; i--)
  {
    str+=to_string(i);
    sums(sum+i, str);
  }
}

int main()
{
  cin >> n;
  string s = "";
  sums(0, s);
}

最佳答案

问题出在您的:for循环内的str+=to_string(i);。

第一次调用时，总和为0，str =“”，在for循环中，它从i = 4开始，i--。但是在主体内部，您附加到str + = 4并调用sums(4，“4”)，则错误发生在下一个循环i-- str + =“3”并变为“43”和sums(3， “43”);

您可以通过不修改str而是通过调用来解决它sums(sum + i, str + to_string(i));

关于c++ - 递归求和任务的错误答案，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52866849/