Неправильный ответ с заданием рекурсивной суммы

Question

Я работаю над проблемой, чтобы напечатать все не увеличивающиеся подпоследовательности с суммой, равной заданному числу 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);
}

Answer 1

Из моего понимания рекурсивных функций я считаю, что цикла вообще не должно быть!Итак, замените:

for (int i = n-sum; i >= 1; i--)
{
  str+=to_string(i);
  sums(sum+i, str);
}

на:

str+=to_string(n-sum);
sums(n-sum, str);

Answer 2

Проблема в вашем: str+=to_string(i); в вашем цикле for.

при первом вызове у вас есть сумма 0, str = "", а в цикле for это происходит из i = 4, i-.но внутри тела вы добавляете к str + = 4 и вызываете суммы (4, "4"), и ошибка возникает в следующем цикле i--, str + = "3" и становится "43" и суммами (3,"43");

Вы можете исправить это, не изменяя str, а вызывая sums(sum + i, str + to_string(i));