DFS 组合枚举P1036 选数 P1157 组合输出 题解复盘前言这两道题都是DFS 组合枚举的经典应用核心思想一致组合 顺序无关用 start 参数控制下一层从哪个位置开始枚举。题目核心问题额外操作P1157 组合输出输出 1~n 中选 r 个数的所有组合按字典序输出P1036 选数从 n 个数中选 k 个求和为素数的方案数素数判断 计数第一部分P1157 组合的输出基本信息项目内容题目编号、来源P1157 洛谷 / 组合的输出训练层级A DFS知识版块DFS、回溯、组合型枚举解题前・关键信号识别维度分析目标、约束、底层结构目标从 1~n 中选 r 个数按字典序输出所有组合约束1 n 210 ≤ r ≤ n底层结构DFS 递归枚举用 start 参数控制下一层从哪个数开始。数据规模n ≤ 20组合数 C(20,10) 184756DFS 完全可行。候选算法和依据DFS 回溯依据组合不计顺序下一层从 i1 开始枚举保证升序且不重复。复杂度预判时间复杂度 O(C(n,r))空间复杂度 O®。解题后・外化复盘维度内容实现结构 / 核心思路第一步定义全局变量 n, rpath[25] 存当前组合第二步定义dfs(step, start)step 表示已经选了几个数start 表示下一个数从几开始枚举第三步若step r输出当前组合第四步枚举 i 从 start 到 npath[step] i递归dfs(step1, i1)第五步从dfs(0, 1)开始。核心思想组合不计顺序下一层从 i1 开始枚举避免重复。错因回溯1. 用排列的 visited 数组组合不需要2. 递归调用写成dfs(step1, start1)而不是i13. 输出格式错误每个数字占 3 个场宽4. r0 时输出空行。边界和易错点1. r0 时输出一个空行2. 每个数字占 3 个场宽用setw(3)3. 下一层起点是i1不是start14. 组合升序自然满足。下次看到什么信号我应该想到这个方法看到「组合 输出所有方案 不分顺序」用 DFS start 参数。AC 完整代码#includeiostream#includeiomanipusingnamespacestd;intn,r;intpath[25];voiddfs(intstep,intstart){if(stepr){for(inti0;ir;i){coutsetw(3)path[i];}coutendl;return;}for(intistart;in;i){path[step]i;dfs(step1,i1);}}intmain(){cinnr;dfs(0,1);return0;}P1036 选数 题解复盘基本信息项目内容题目编号、来源P1036 洛谷 / NOIP2002 普及组训练层级A DFS知识版块DFS、组合枚举、素数判断解题前・关键信号识别维度分析目标、约束、底层结构目标从 n 个数中选 k 个求和为素数的方案数约束n ≤ 20底层结构组合枚举 素数判断。数据规模n ≤ 20组合数 C(20,10) 184756DFS 完全可行。候选算法和依据DFS 回溯依据选 k 个数求和顺序无关属于组合枚举。复杂度预判时间复杂度 O(C(n,k) × k)空间复杂度 O(k)。解题后・外化复盘维度内容实现结构 / 核心思路第一步读入 n, k 和数组 v第二步定义dfs(step, start)step 表示已选了几个数start 表示当前从哪个下标开始枚举第三步若step k计算 path 中 k 个数的和判断是否为素数若是则 ans第四步枚举 i 从 start 到 npath[step] v[i]递归dfs(step1, i1)第五步输出 ans。核心思想组合枚举所有选法每选够 k 个就求和判断素数。错因回溯1. 用排列的 visited 数组导致重复计算2. 递归写成dfs(step1, start1)而不是i13. path 下标写成path[i] v[i]而不是path[step] v[i]。边界和易错点1. 素数判断1 不是素数2 是素数2. 组合用 start 参数不需要 visited3. 下一层递归传i14. 求和时注意数组下标统一。下次看到什么信号我应该想到这个方法看到「从 n 个数中选 k 个 顺序无关 判断条件」用 DFS 组合枚举。AC 完整代码#includeiostreamusingnamespacestd;intn,k,ans;intpath[25],v[25];boolisprime(intnum){if(num1)returnfalse;if(num2)returntrue;if(num%20)returnfalse;for(inti3;i*inum;i2){if(num%i0)returnfalse;}returntrue;}voiddfs(intstep,intstart){if(stepk){intsum0;for(inti0;ik;i){sumpath[i];}if(isprime(sum))ans;return;}for(intistart;in;i){path[step]v[i];dfs(step1,i1);}}intmain(){cinnk;for(inti0;in;i){cinv[i];}dfs(0,0);coutansendl;return0;}
