1. 从“烤鸡”到“枚举”一道经典算法题的解题心路看到“洛谷P2089 烤鸡”这个标题你可能会一愣以为点进了什么美食社区。但混迹算法竞赛圈的老鸟们会心一笑这其实是洛谷上一道非常经典的入门级搜索与枚举题目。它用了一个生活化的场景——配置烤鸡的调料来包装一个核心的算法思想如何系统地遍历所有可能的组合。这道题对于刚接触算法的新手来说是一块极佳的“磨刀石”能让你深刻理解暴力枚举的边界、递归与循环的实现差异以及如何将实际问题抽象为程序模型。今天我就结合自己当年刷题和后来带新人的经验抛开题解区那些“炫技”的简短代码用两种最本质的方法递归回溯与多重循环配上保姆级的注释和完整的C实现带你吃透这道题。无论你是正在备战蓝桥杯、CSP-J/S的学生还是希望巩固基础的程序员这篇内容都能让你对“枚举”这个算法基石有新的认识。2. 问题重述与核心抽象调料配比中的数学题目描述很有趣猪猪Hanke特别喜欢吃烤鸡他吃鸡很特别为什么特别呢因为他有10种配料芥末、孜然等每种配料可以放1到3克必须是整数克。烤鸡的美味程度为所有配料的质量之和。现在给出美味程度n (n≤5000)你的任务是输出所有配料组合的方案。如果方案数大于0先输出方案总数然后按字典序可以理解为配方字符串的升序输出所有方案如果方案数为0则输出0。2.1 问题本质的数学建模让我们剥开“烤鸡”这个有趣的外壳看看它的数学内核变量我们有10个变量记为 a₁, a₂, ..., a₁₀。每个变量的定义域每个 aᵢ 可以取 {1, 2, 3} 中的任意一个整数。这是离散的、有限的取值集合。约束条件所有变量的和必须等于给定的整数 n即 a₁ a₂ ... a₁₀ n。目标找出所有满足上述约束的 (a₁, a₂, ..., a₁₀) 有序元组并统计其数量最后按特定顺序字典序输出。这本质上是一个带有约束的完全枚举问题。10个变量每个3种可能理论上的搜索空间是 3¹⁰ 59049 种组合。对于n≤5000这个规模完全在计算机的可处理范围内因此我们可以放心地使用枚举法。2.2 “字典序”输出的理解与实现关键题目要求按字典序输出。在这个上下文中什么是字典序我们可以把每一种配方看作一个长度为10的字符串每个字符是‘1’‘2’或‘3’。字典序就是字符串比较的规则从第一个位置第一种配料开始比较数字小的排在前面如果相同则比较下一个位置以此类推。例如配方 (1,1,1,1,1,1,1,1,1,1) 的字典序是最小的而 (3,3,3,3,3,3,3,3,3,3) 是最大的。这对我们的算法实现提出了一个隐含要求我们生成的方案序列本身就应该是有序的或者生成后能方便地排序。最直接的方法是让我们的搜索过程本身就按照字典序递增的顺序来遍历所有可能解。这样我们就不需要额外排序生成一个就输出或存储一个效率最高。注意很多新手在这里会踩坑他们可能用了一种“乱序”的搜索方式比如随机尝试最后再调用sort。这虽然结果正确但增加了不必要的复杂度也违背了算法设计的优雅性。我们的目标应该是让算法逻辑与输出要求自然契合。3. 方法一深度优先搜索DFS与递归回溯这是解决此类组合枚举问题最自然、最通用的思想尤其当变量个数不固定或者约束更复杂时DFS回溯法的优势就体现出来了。其核心是尝试与回退。3.1 算法思路与递归树我们可以把寻找10种配料克数的过程想象成在一棵树上进行深度优先遍历。树的层级树一共有10层分别对应第1种到第10种配料的选择。树的每个节点代表一种“部分配方”即已经确定了前k种配料的克数。节点的分支每个节点在确定第k种配料时有3个子节点分别代表放1克、2克或3克。树的叶子节点代表一种完整的配方10种配料全部确定。剪枝在遍历过程中如果发现当前已确定配料的总和已经超过n或者即使后面所有配料都只放最小的1克总和也无法达到n那么这条路径就不可能产生有效解可以立即停止向下搜索回溯尝试其他选择。这能显著减少不必要的搜索。3.2 代码实现与逐行精讲下面是用C实现的DFS回溯解法。我会在关键位置插入详细注释解释每一部分的意图和细节。#include iostream #include vector using namespace std; int n; // 美味程度即配料总克数 int total 0; // 方案总数 vectorvectorint solutions; // 存储所有找到的配方方案 vectorint current(10); // 当前正在构建的配方长度为10的数组 // 深度优先搜索函数 // 参数 index 表示当前正在决定第几种配料0-9 // 参数 sum 表示当前已确定配料的总克数 void dfs(int index, int sum) { // 递归终止条件1已经确定了10种配料 if (index 10) { // 检查总和是否恰好等于n if (sum n) { total; // 方案数加1 solutions.push_back(current); // 存储当前方案 } // 无论是否等于n10种配料已定都必须返回结束这条路径 return; } // 递归终止条件2剪枝即使后面所有配料都只放1克也无法达到n // 当前已选总和sum 剩余配料个数(10-index) * 1 n 则不可能成功 // 同理如果当前总和已经超过n也直接返回剪枝 if (sum n || sum (10 - index) * 1 n) { return; } // 递归终止条件3剪枝即使后面所有配料都放最大的3克也达不到n // 这个条件有时可以省略因为上一个条件通常更早触发但加上更严谨 // if (sum (10 - index) * 3 n) return; // 对于第index种配料尝试放入1克、2克、3克 // 注意这里循环从1到3保证了在同一层级我们先尝试小的数从而自然实现字典序生成 for (int weight 1; weight 3; weight) { current[index] weight; // 做出选择第index种配料放weight克 dfs(index 1, sum weight); // 递归处理下一种配料 // 注意这里没有典型的“撤销选择”操作因为current[index]会在下一次循环中被覆盖。 // 这是一种更简洁的写法利用了数组位置会被重写的特性。 } } int main() { cin n; // 初始调用DFS从第0种配料开始当前总和为0 dfs(0, 0); // 输出结果 if (total 0) { cout 0 endl; } else { cout total endl; // 由于我们的DFS搜索顺序本身就是字典序所以直接输出即可 for (int i 0; i total; i) { for (int j 0; j 10; j) { cout solutions[i][j] ; } cout endl; } } return 0; }3.3 关键细节与避坑指南递归函数参数的设计index和sum是核心。index控制递归深度进度sum记录当前状态用于剪枝和最终判断。将它们作为参数传递比使用全局变量在递归中修改更清晰也更容易理解状态的变化。剪枝的艺术代码中的两个剪枝条件是效率的关键。sum n当前总和已超标后面再加只会更大立刻返回。sum (10 - index) * 1 n这是一个“乐观估计”剪枝。假设后面所有未确定的配料都只放最少的1克如果这样总和还超过n那肯定没戏。这个条件非常强大能提前砍掉大量无效分支。注释掉的第三个条件是“悲观估计”剪枝即使后面全放3克也达不到n。在本问题中由于n上限很大5000这个条件不如前两个有效但对于n很小的情况可能有优化作用。编程时要有选择地使用剪枝。字典序的保证注意for (int weight 1; weight 3; weight)这行循环。它让每一层递归都先尝试1再尝试2最后尝试3。这就像我们写数字时先写高位一样自然保证了最终生成的所有完整方案是按照“配方字符串”字典序递增的。这是一个非常重要的技巧。存储方案我们使用vectorvectorint来存储所有方案。在递归终点index10且sumn时将current数组的一个副本存入solutions。这里必须存副本push_back(current)会调用拷贝构造函数因为current在后续递归中会被修改。空间与时间的权衡此方法存储了所有方案占用内存约为 方案数 × 10 × 4字节。当n使得方案数极大时理论上最大方案数是一个组合数学问题内存可能成为瓶颈。另一种更节省空间的写法是找到一个方案就立刻输出一个但这要求输出顺序必须正确。我们的写法因为保证了生成顺序所以两种方式都可行存储起来更方便处理。4. 方法二十重循环暴力枚举对于变量数量固定比如就是10个且每个变量取值范围很小的情况最“笨”但也最直观的方法就是写多重循环。这体现了计算机最原始的强大能力不厌其烦地快速尝试所有可能。4.1 算法思路模拟所有组合我们直接写10层for循环每一层循环对应一种配料的可选克数1,2,3。这样循环的最内层我们就得到了一个具体的配方 (a1, a2, ..., a10)。然后我们检查它们的和是否等于n如果等于就记录下来或直接输出。4.2 代码实现与剖析#include iostream #include vector using namespace std; int main() { int n; cin n; vectorvectorint ans; // 存储有效方案 int count 0; // 方案计数器 // 十重循环每一重代表一种配料 for (int a1 1; a1 3; a1) for (int a2 1; a2 3; a2) for (int a3 1; a3 3; a3) for (int a4 1; a4 3; a4) for (int a5 1; a5 3; a5) for (int a6 1; a6 3; a6) for (int a7 1; a7 3; a7) for (int a8 1; a8 3; a8) for (int a9 1; a9 3; a9) for (int a10 1; a10 3; a10) { // 在最内层循环计算当前配方的总克数 int sum a1 a2 a3 a4 a5 a6 a7 a8 a9 a10; if (sum n) { count; // 创建一个临时vector存储当前方案 vectorint solution {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}; ans.push_back(solution); } } // 输出结果 if (count 0) { cout 0 endl; } else { cout count endl; for (const auto sol : ans) { for (int gram : sol) { cout gram ; } cout endl; } } return 0; }4.3 方法评价与适用场景优点极其直观逻辑一目了然几乎就是问题描述的直译。非常适合初学者理解“枚举”这个概念。无需剪枝因为循环本身就遍历了所有3^10种组合检查条件即可。自然有序循环变量从最外层到最内层依次是a1到a10且每一层都是从1循环到3。这同样保证了生成的方案序列是严格的字典序。缺点代码冗长10层循环写起来很枯燥而且如果题目稍微一变比如配料变成12种代码就要重写。缺乏灵活性无法应对变量数量动态变化的问题。可读性差对于有经验的程序员来说看到10层循环会觉得不够优雅。那么什么时候该用这种方法当你百分之百确定变量的个数是固定的、且数量不多比如小于等于6时多重循环写法简单粗暴有效。在竞赛中如果时间紧迫针对这种固定小规模枚举直接写循环反而更快更不容易出错。但对于像本题这样有10层的情况写起来确实有点累这更多是一种教学展示告诉你枚举的本质就是循环嵌套。5. 两种方法的对比与深层思考解决了问题我们不妨再深入一层对比一下这两种方法并思考它们背后更通用的模式。5.1 效率对比时间复杂度两种方法在最坏情况下都需要遍历所有59049种组合因此时间复杂度都是 O(3^k)其中k10。DFS通过剪枝可以在某些情况下提前退出分支但平均来看对于本题的规模两者运行时间相差无几都能在瞬间完成。空间复杂度DFS递归需要栈空间深度为10可以忽略不计。两者主要的存储空间都在于保存结果。十重循环的局部变量更多但也在常数级别。总体而言空间复杂度都是 O(方案数 * k)。5.2 思想延伸DFS回溯法代表了一类状态空间搜索的通用范式。它不仅仅用于组合枚举还广泛应用于路径查找迷宫、排列生成、子集选择、图遍历等。其核心框架是定义状态当前配方、当前总和。列出所有可选操作放1、2、3克。做出一个选择进入下一层状态递归。到达终点或非法状态时返回回溯。尝试下一个选择。 掌握这个框架你就掌握了解决一大类搜索问题的钥匙。多重循环法则是穷举法最直接的体现。它适用于解空间是笛卡尔积的情况即每个变量独立取值所有组合的集合。当变量间有复杂约束时多重循环内可以加入if判断进行过滤但DFS的剪枝通常更灵活、更早。5.3 如何选择一个实用的决策流程面对一个枚举问题我通常会这样思考变量个数是否固定且很少≤5是 → 考虑直接用多重循环代码简单。变量个数是否不固定或者很多是 → 必须用DFS回溯或类似的递归/迭代生成方法。是否存在可以在搜索中途判断的无效状态剪枝机会是 → DFS回溯优势明显可以大幅减少搜索量。是否需要输出所有解并且对顺序有要求是 → 在设计DFS的尝试顺序或循环顺序时就要将顺序考虑进去就像我们做的从1到3循环。对于“烤鸡”这道题虽然变量个数固定为10但写10层循环实在不美且DFS能更好地体现“搜索”和“剪枝”的思想因此DFS回溯是更受推荐的通解。多重循环解法则有助于初学者夯实“枚举”的基本概念。6. 优化与变种探讨当n很大或很小时虽然本题数据范围下两种方法都轻松通过但我们可以思考一下边界情况和优化可能。6.1 极端情况分析当n 10 或 n 30时显然无解。因为10种配料都放1克总和是10都放3克总和是30。如果n不在此区间可以直接输出0。这是一个非常有效的预判剪枝可以在调用DFS或循环前就完成避免无谓的搜索。当n 10 或 n 30时只有唯一解分别是全1和全3。我们的算法仍然会遍历很多状态但剪枝条件sum (10-index)*1 n在n10时会非常有效几乎一路剪枝。对于n30则是sum n这个条件会早早剪掉非全3的路径。6.2 使用迭代而非递归有些时候出于避免递归栈溢出虽然本题深度10不可能或追求极致效率的考虑可以用栈来手动模拟递归过程也就是迭代加深搜索IDS或直接用栈实现回溯。但对于本题递归写法清晰易懂是最佳选择。6.3 动态规划DP的视角我们还可以从另一个角度看这个问题求方案数。这变成了一个经典的有限制条件的整数划分问题将整数n划分为10个部分每个部分在[1,3]区间。 我们可以定义DP状态dp[i][j]表示用前i种配料凑出总重量为j的方案数。 状态转移方程dp[i][j] dp[i-1][j-1] dp[i-1][j-2] dp[i-1][j-3]前提是j-1, j-2, j-3 (i-1)*1确保前面i-1种配料至少各放1克是可行的这是一个更精细的边界。 初始状态dp[0][0] 1。 最终答案dp[10][n]。 DP方法可以在O(10 * n)的时间复杂度内求出方案总数比枚举快得多。但是DP通常只用于计数要输出所有具体方案还是需要结合搜索。不过我们可以先用DP判断方案数是否为0如果为0则直接输出避免无效的搜索开销。这是一种“预判搜索”的混合策略。7. 从“烤鸡”到通用解题框架的提炼最后我们来总结一下从这道题中学到的、可以迁移到其他问题上的经验。7.1 问题抽象能力这是算法学习的第一步。无论题目披着什么样的故事外衣烤鸡、放苹果、走迷宫都要能迅速剥离出核心的数学模型几个变量每个变量的取值范围变量间的约束关系等式、不等式目标是什么求所有解、解的数量、最优解“烤鸡”问题就是一个经典的多元一次方程整数解枚举模型。7.2 搜索算法的框架思维DFS回溯是一个强大的框架。其伪代码几乎可以套用于很多问题void dfs(当前状态) { if (到达终止状态) { 记录或输出解; return; } if (当前状态不合法) { // 剪枝 return; } for (所有可能的选择) { 做出选择更新状态; dfs(下一状态); // 撤销选择恢复状态如果需要 } }“烤鸡”问题中“状态”是(index, sum)“选择”是weight1,2,3“终止状态”是index10“合法性判断”是各种剪枝条件。7.3 对枚举顺序的敏感度题目要求字典序输出这直接影响了我们搜索时尝试选择的顺序从小到大循环。在很多其他问题中比如求“最小字典序解”这个技巧至关重要。它提醒我们在设计搜索时要时刻考虑输出要求让搜索顺序为其服务。7.4 简单问题背后的扩展这道题很简单但我们可以自己给自己出“加强版”版本A每种配料的克数范围不同比如第i种可以放lᵢ到rᵢ克。只需要修改DFS中for循环的上下界。版本B配料种类数k由输入决定。这时十重循环写法就彻底失效必须用DFS。版本C在满足总和为n的前提下求一种特定的最优解比如某种配料尽可能少。这需要在DFS过程中维护和比较一个最优值。 通过思考这些变种你能更牢固地掌握解法的核心而不是死记硬背一道题的代码。编程解题就像做菜题目“烤鸡”给了你原料变量、约束和菜谱枚举算法。真正掌握的做法是理解菜谱背后的烹饪原理搜索、剪枝这样无论下次遇到“烤鸭”还是“烧鹅”你都能自己调配出合适的算法大餐。希望这篇详细的拆解能帮你把“烤鸡”这道菜的火候掌握得恰到好处。