递归函数题 整数拆分

题解 整数拆分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≤ai1a_i \le a_{i1}ai​≤ai1​。如何保证字典序在每一层搜索中我们从小到大枚举当前位可能的数字。DFS 的天然特性先探索较小的分支会自动保证输出结果符合字典序。3. 代码实现 (C)#includeiostream#includevectorusingnamespacestd;/** * param remain 剩余待拆分的数值 * param start 当前拆分允许的最小值保证单调不减 * param path 记录当前的拆分路径 */voiddfs(intremain,intstart,vectorintpath){// 递归边界当剩余数值为 0 时说明找到了一组完整拆分if(remain0){for(inti0;ipath.size();i){coutpath[i](ipath.size()-1?: );}coutendl;return;}// 从 start 开始尝试确保序列单调不减同时满足字典序从小到大for(intistart;iremain;i){path.push_back(i);// 选择当前数字dfs(remain-i,i,path);// 递归剩余量减少下一个起点仍为 ipath.pop_back();// 回溯撤销选择尝试更大的 i}}intmain(){intn;if(cinn){vectorintpath;dfs(n,1,path);// 从 1 开始拆分}return0;}