本题链接： 自然数的拆分 DFS（深度优先搜索） 本题是一道经典的深搜，一路搜到底得到一种方案，本次方案排列完毕后，回溯搜索下一方案。由于本蒟蒻现在对DFS的理解不深，这里引用一篇博文 DFS讲解
#include<bits/stdc++.h> using namespace std; int a[10001] = { 1 }, n; int search(int, int); int print(int); int main() { cin >> n; search(n, 1);//将要拆分的数n传递给s return 0; } int search(int s, int t) { int i; for (i = a[t - 1]; i <= s; i++) if (i < n)//当前数i要大于等于前一位数，且不超过n { a[t] = i;//保存当前拆分的数i s -= i;//s减去数i，s的值将继续拆分 if (s == 0)print(t);//当s=0时，拆分结束输出结果 else search(s, t + 1);//当s>0时，继续递归 s += i;//回溯：加上拆分的数，以便产生所有可能的拆分 } } int print(int t) { for (int i = 1; i <= t - 1; i++)//输出一种拆分方案 cout << a[i] << "+"; cout << a[t] << endl; }核心代码：
int search(int s, int t) { int i; for (i = a[t - 1]; i <= s; i++) if (i < n)//当前数i要大于等于前一位数，且不超过n { a[t] = i;//保存当前拆分的数i s -= i;//s减去数i，s的值将继续拆分 if (s == 0)print(t);//当s=0时，拆分结束输出结果 else search(s, t + 1);//当s>0时，继续递归 s += i;//回溯：加上拆分的数，以便产生所有可能的拆分 } }