https://www.luogu.com.cn/problem/P2404
蒟蒻献上一道水题，灰常水。题目详见链接。
大意如下：任何一个大于1的正整数n，总可以拆分成若干个小于n的正整数之和。 按字典序输出解。
对于本题而言简单的一个dfs+回溯。
上代码，详见批注
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 using namespace std; 5 int n, m; 6 int p[1000] = { 1 }; 7 void sc(int t) { 8 for (int i = 1; i < t; i++) 9 cout << p[i] << "+"; 10 cout << p[t] << endl; 11 }//输出木有问题的啦 12 void dfs(int a) {//a用来记录数--拆分成的数 13 for (int i = p[a - 1]; i <= m; i++) {//回溯后跳出分支 14 if (i == n) continue;//防止最后一行输出n 15 p[a] = i;m -= i; 16 if (m == 0) sc(a);//当m减完，遍历结束，进入输出 17 else dfs(a + 1); 18 m += i;//回溯 19 } 20 } 21 int main() { 22 cin >> n;//输入木有问题的啦 23 m = n; 24 dfs(1); 25 return 0; 26 }
本题为《信息学奥赛一本通》例题，书中代码如下：
#include<cstdio> #include<iostream> #include<cstdlib> 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; }