自然数的拆分

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n;
void sdf(int x,int y) {//x表示第几个盒子 y代表当前数字还剩多少
  if (y == 0&&x>2) {//到达目的地的判断条件
    cout << n << "=";
    for (int i = 1; i <x-1 ; i++) {
      cout << a[i] << "+";
    }
    cout << a[x - 1] << endl;//由于最后没有+，所以最后一个数字要单独输出
  }
  for (int i = 1; i <= y; i++) {
    if (i >= a[x - 1]) {//后面的数字大于等于前面的数字
      a[x] = i;
      y = y - i;//每次拆分都让y-i
      sdf(x + 1, y);
      a[x] = 0;//以下两步是回溯，也就是恢复原样
      y = y + i;
    }
  }
}
int main() {
  cin >> n;
  a[0] = 1;
  sdf(1, n);
  return 0;
}