题目描述
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。 输入格式
输入：待拆分的自然数n。 输出格式
输出：若干数的加法式子。 输入输出样例 输入 #1
7
输出 #1
1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+1+3 1+1+1+2+2 1+1+1+4 1+1+2+3 1+1+5 1+2+2+2 1+2+4 1+3+3 1+6 2+2+3 2+5 3+4
说明/提示
用回溯做。。。。
n≤8
对于dfs设计的理解：在写dfs的时候要理解要针对什么进行搜索，这里是对大于等于前一个被加数的自然数进行搜索。
代码实现：
#include <iostream> using namespace std; int n, m, a[11] = {1}; void dfs(int step) { if (a[1] == m) return; if (n == 0) { cout << a[1]; for (int i = 2; i < step; i++) cout << '+' << a[i]; cout << endl; return; } for (int i = a[step - 1]; i <= n; i++) //注意搜索第一次枚举数目的大小 { if (n >= i) { a[step] = i; n -= i; //类似于book标记 dfs(step + 1); n += i; } } } int main() { cin >> n; m = n; dfs(1); return 0; }