题目描述
任何一个大于 (1) 的自然数 (n) ，总可以拆分成若干个小于 (n) 的自然数之和。当 (n = 4) 时，总共有 (4) 种拆分方法：
- (4=1+1+1+1)
- (4=1+1+2)
- (4=1+3)
- (4=2+2)
现在给你一个数 (n(1 le n le 20)) ，请按顺序输出 (n) 的所有拆分方案。
输入格式
输入包含一个整数 (n(1 le n le 20)) 。
输出格式
输出 (n) 的所有拆分方案，每种方案占一行，输出格式见样例输出。
样例输入
4
样例输出
4=1+1+1+1
4=1+1+2
4=1+3
4=2+2
题目分析
首先我们分析一下，因为 (n le 20) 所以 (n) 最多也只能拆分成 (n) 个数之和，所以我开一个大小比 (20) 大一点的数组 ans[22] 就可以存放所有的加数了。
然后我再开一个函数 void f(int id, int tmp) 用来存放 ans[] 数组的第 id 个值，而这里的 tmp 用于表示我目前还剩下的可以用的数。比如，我调用了 f(3, 5)，然后我将 ans[3] 设为了 2 （此时我将第 (3) 个加数设为了 (2) ），那我接下来就递归调用 f(4, 3) 了。因为我用掉了 (5) 里面的 (2) , 所以我剩下来的可以用的数就只剩下了 (5-2=3) 了。
然后我们再来看一下 f(id, tmp) ，表示我要在第 id 个位置选一个数放，但是这个数的范围是有限制的，假设我要在第 (id) 个位置放一个数 (i) ，那么这个 (i) 是有范围限制的，它需要满足一定的条件：
- 当 (id>1) 时，必须满足 (i ge ans[id-1]) ，因为公式里面的每一个加数都必须大于等于前一个加数；
- 除非第 (id) 个位置的数是最后一个数（即将 (i) 作为 (ans[id])），否则，为了满足 (i) 小于等于下一个加数的条件，必须使条件 (i le tmp-i) （即 (i le lfloor cfrac n2 floor) ）满足。
- 当 (id = 1) 时，为了满足至少有两个加数的条件，必须满足 (1 le i le lfloor cfrac n2 floor) 。
据此，我们可以编写深度优先搜索代码如下：
#include <bits/stdc++.h>
using namespace std;
int n, ans[22];
void f(int id, int tmp) { // 当前放第id个数，剩余和为tmp
if (id == 1) { // id==1时，i从1到tmp/2
for (int i = 1; i <= tmp/2; i ++) {
ans[id] = i; // 将ans[id]设为i
f(id+1, tmp-i); // 然后进下一层搜索
}
}
else { // id>1时，i从ans[id-1]到tmp/2
for (int i = ans[id-1]; i <= tmp/2; i ++) {
ans[id] = i;
f(id+1, tmp-i);
}
// id>1时可将tmp设为ans[id]，并输出方案
ans[id] = tmp;
cout << n << "=";
for (int i = 1; i <= id; i ++) {
cout << (i > 1 ? "+" : "") << ans[i];
}
cout << endl;
}
}
int main() {
cin >> n;
f(1, n); // 表示选第一个数的时候剩余数值为n
return 0;
}