自然数拆分问题

又刷了刷PTA上的题目，重写了一遍题感觉比之前代码简洁不少。

题目

一个整数N(N > 1)可以拆分成若干个大于等于1的自然数之和，请你输出所有不重复的拆分方式。

所谓拆分方式的重复性判定如下：给定N=a​1​​+a​2​​+…a​m1​​ 和 N=b​1​​+b​2​​+…b​m2​​ 表示整数N的两种拆分方式。对于∀a​i​​,b​j​​≥1，令集合A={a​i​​∣1≤i≤m​1​​},B={b​j​​∣1≤j≤m​2​​}。若满足集合A=B，则称这两种拆分方式是重复的。

例如 6 = 3 + 2 和 6 = 2 + 3, 就是重复的拆分方式。

输入格式:

一个正整数N（1≤N≤52）。

注意：本题N的上限52，是经过PTA平台服务器测试后得到的上限，能够保证较好的搜索策略在PTA提交，在1s内求解。本地PC机上，即使较好方法运行时间也可能大于1s，如果觉得方法没问题，可以先提交试试。

输出格式:

按照拆分方案的字典序由小大到大，输出所有方案，请参考输出样例

输入样例:

在这里给出一组输入。例如：

6

输出样例:

在这里给出相应的输出。例如：

6=1+1+1+1+1+1
6=1+1+1+1+2
6=1+1+1+3
6=1+1+2+2
6=1+1+4
6=1+2+3
6=1+5
6=2+2+2
6=2+4
6=3+3
6=6

题解

典型的回溯法，穷举所有可能性。注意的是这里要去除重复，观察一下如果已经对1的情况穷举完，下一次就从2开始并且不能包括1。这个特点和之前做过的很多题都类似。

#include <algorithm>
#include <iostream>
using namespace std;
void backtrace(int index, string &str, int now);

int num;
int main() {
  cin >> num;
  string str;
  backtrace(num, str, 1);
  system("pause");
}

void backtrace(int index, string &str, int now) {
  if (index == 0) {
    // cout <<num<<"=" + str << endl;  //慢的不行cout
    printf("%d=%s",num,str.c_str());   //c里面没有string，需要转化一下
    putchar(10);
  }
  for (int i = now; i <= index; i++) {
    string temp = str;
    if (!str.empty()) {
      str += '+';
    }
    str += to_string(i);
    backtrace(index - i, str, i);
    str = temp;
  }
}

实测cout比printf慢的不是一点半点。不过我还是喜欢c++。