题目描述
任何一个大于 1的自然数 n，总可以拆分成若干个小于 n 的自然数之和。现在给你一个自然数 n，要求你求出 n 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。
输入格式
输入：待拆分的自然数 n。
输出格式
输出：若干数的加法式子。
输入输出样例
输入
7
输出
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
说明/提示
数据保证，2≤n≤8。
#include<iostream> #include<vector> #include <algorithm> using namespace std; void dfs(int n, int start, vector<int>& path) { if (n == 0) { for (int i = 0; i < path.size(); i++) { cout << path[i]; if (i != path.size() - 1) { cout << "+"; } } cout << endl; return ; } for (int i = start; i <= n; ++i) { path.push_back(i); dfs(n - i, i, path); path.pop_back(); } } int main() { int n; cin >> n; vector<int> path; dfs(n, 1, path); return 0; }
这个代码运行后会输出n的数值，与题目要求不符，改进后代码如下：
#include<iostream> using namespace std; class Solution { public: int n, a[10]; void dfs(int h, int c, int q) { if (h == n) { for (int i = 1; i <= c - 2; i++) { cout << a[i] << '+'; } cout << a[c - 1] << endl; return; } if (h > n) return; for (int i = q; i <= n - 1; i++) { a[c] = i; dfs(h + i, c + 1, i); a[c] = 0; } } }; int main() { Solution solution; cin >> solution.n; solution.dfs(0, 1, 1); return 0; }
