递归函数题 整数拆分
题解： 整数拆分
1. 题目大意
给定一个正整数nnn(1≤n≤101 \le n \le 101≤n≤10)，要求输出所有可能的拆分方案。
- 规则：拆出的数字序列必须是单调不减的（即a1≤a2≤⋯≤aka_1 \le a_2 \le \dots \le a_ka1≤a2≤⋯≤ak）。
- 顺序：所有方案按字典序大小依次输出。
2. 核心算法：DFS 与 回溯
由于nnn的范围较小 (n≤10n \le 10n≤10)，最适合使用深度优先搜索 (DFS)来穷举所有可能。
- 如何保证单调不减？
在递归时，记录上一次拆分出来的数字start。下一层拆分选取的数字必须从start开始尝试，这样生成的序列自然满足ai≤ai+1a_i \le a_{i+1}ai≤ai+1。 - 如何保证字典序？
在每一层搜索中，我们从小到大枚举当前位可能的数字。DFS 的天然特性（先探索较小的分支）会自动保证输出结果符合字典序。
3. 代码实现 (C++)
#include<iostream>#include<vector>usingnamespacestd;/** * @param remain 剩余待拆分的数值 * @param start 当前拆分允许的最小值（保证单调不减） * @param path 记录当前的拆分路径 */voiddfs(intremain,intstart,vector<int>&path){// 递归边界：当剩余数值为 0 时，说明找到了一组完整拆分if(remain==0){for(inti=0;i<path.size();i++){cout<<path[i]<<(i==path.size()-1?"":" ");}cout<<endl;return;}// 从 start 开始尝试，确保序列单调不减，同时满足字典序从小到大for(inti=start;i<=remain;i++){path.push_back(i);// 选择当前数字dfs(remain-i,i,path);// 递归：剩余量减少，下一个起点仍为 ipath.pop_back();// 回溯：撤销选择，尝试更大的 i}}intmain(){intn;if(cin>>n){vector<int>path;dfs(n,1,path);// 从 1 开始拆分}return0;}