烤鸡怎么烤才美味？试试「递归」~【CSP-J复习】
本帖最后由 高山 于 2026-9-27 18:50 编辑给你一只烤鸡
现在你要开始放调料了
问顾客对烤鸡需要一定的美味程度
你有多少种搭配的方案呢？具体如何搭配呢？
（强烈建议所有烧烤店学习C++）
好了，「言归正传」，等你先把程序设计出来在考虑怎么和烧烤店合作吧。
推荐视频：https://www.bilibili.com/video/BV15Y4y1z71Z/?spm_id_from=333.337.search-card.all.click&vd_source=4cfbfe21af0fd1db1e7483eee38d3aab*推荐前往Bilibili观看，本版与视频作者不存在任何利益关系，仅做优秀视频推荐。
让我们康康题：>>>可使用配套OJ练习本题
P2089 烤鸡
题目背景
猪猪 Hanke 得到了一只鸡。
猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）。
题目描述
Hanke 吃鸡很特别，为什么特别呢？因为他有 10 种配料（芥末、孜然等），每种配料可以放 1 到 3 克，任意烤鸡的美味程度为所有配料质量之和。
现在，Hanke 想要知道，如果给你一个美味程度 n，请输出这 10 种配料的 所有搭配方案。
输入格式
一个正整数 n，表示美味程度。
输出格式
第 1 行一个整数，表示方案总数。
第 2 行至结束每行 10 个数，表示每种配料所放的质量，按字典序排列。
无解时只在第一行输出一个 0。
输入输出样例
输入：
11输出：
10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
说明 / 提示
数据范围对于 100% 的数据，$n \le 10000$。
有效范围每种配料只能放 1、2 或 3 克，共 10 种，故美味程度的有效范围为 $$，超出此范围则无解。
如果还没有「思路」，就来根据下面的点拨开始吧~
请注意，写10重for循环是非常不明智的选择哦！
部分题解由AI生成，和人类共同完成本次题解。
如果你有好的「想法」或「疑问」，欢迎点击回复哦~我们将对这类回复奖励鱼币和贡献！
如果喜欢，不要忘记「评分」~
前言
这道题是 DFS（深度优先搜索）的入门经典题。看似是"烤鸡"，本质就是：
从 10 个位置里填数字，每个位置只能填 1、2、3，要求总和等于 n，把所有可能都找出来。
下面我带你 一行一行 把代码写出来，每一步都解释为什么这么做。
http://yb.woa.com/FG01GyFoHMT
▲ 图1：十种配料，每种只能选 1g / 2g / 3g，这就是我们要找的"10 个位置"
一、先把问题翻译成数学语言
我们要找的是这样一串数字：
$a_1, a_2, a_3, \dots, a_{10}$
满足两个条��：
[*]每个数字只能取 1、2、3，即 $a_i \in \{1, 2, 3\}$
[*]它们的和等于 $n$，即 $a_1 + a_2 + \dots + a_{10} = n$
比如样例 $n = 11$，一种方案就是 9 个 1 加 1 个 2，即：
1 1 1 1 1 1 1 1 1 2
那问题来了：这一个 2 放在 10 个位置中的哪一个，都是一种不同方案。
所以方案数就是 $\binom{10}{1} = 10$ 种，正好和样例输出的 10 行对上。
http://yb.woa.com/H1z7RiLTwfm
▲ 图2：搜索决策树。从第一个位置开始，每个位置都分出 1、2、3 三条路，一直走到第 10 层
二、为什么用 DFS？能不能用循环？
你可能会想：10 个位置，每个位置 3 种取值，那我写 10 层 for 循环不就行了？
for (int a1 = 1; a1 <= 3; a1++)
for (int a2 = 1; a2 <= 3; a2++)
...
for (int a10 = 1; a10 <= 3; a10++)
// 检查总和
这样确实能过，但写 10 层循环既不优雅也容易写错。
观察一下：每一层的逻辑完全一样——都是"从 1 到 3 试一遍，然后去下一层"。
这正好可以用递归来表达，写成一层就行。
三、手写第一版代码（只输出方案数）
我们先不存方案，只数一数有多少种，把框架搭出来。
#include <iostream>
using namespace std;
int n, cnt; // n 是目标美味程度，cnt 是方案数
// dep 表示当前正在填第几个位置（从 0 数到 9）
// sum 表示目前已经填好的数字之和
void dfs(int dep, int sum) {
if (dep == 10) { // 10 个位置都填完了
if (sum == n) cnt++; // 总和恰好等于 n，方案数加一
return; // 无论是否合法都要返回
}
for (int x = 1; x <= 3; x++) { // 当前这个位置，尝试填 1、2、3
dfs(dep + 1, sum + x); // 填好了，带着新的位置和新总和去下一层
}
}
int main() {
cin >> n;
cnt = 0;
dfs(0, 0);
cout << cnt << endl;
return 0;
}
逐行解释关键三句：
[*]if (dep == 10) —— 递归的"出口"。已经填完了第 10 个位置，说明一条完整路径走到底了，该结算了。
[*]for (int x = 1; x <= 3; x++) —— 这是核心。当前这个位置我依次试 1、2、3，每一个都往下走一遍。
[*]dfs(dep + 1, sum + x) —— 位置前进一格，总和加上这次选的数，继续递归。
http://yb.woa.com/8K0DAXNxeC6
▲ 图3：从左到右依次确定数字，越靠左越早被决定，这就是字典序的来源
四、为什么这样搜出来就是字典序？
这是本题最容易懵的地方，我举个例子你就懂了。
假设我们搜到某个位置，要在 1、2、3 里选。因为我们 从小到大 试：
[*]先试 1，把后面所有情况都搜完，记录下来；
[*]再试 2，把后面所有情况搜完，记录下来；
[*]最后试 3，把后面所有情况搜完，记录下来。
那先被记录下来的方案，一定是"前面尽量小"的。
前面越小的方案排在越前面 —— 这就是字典序的定义。
结论：我们不需要任何排序，只要按 1→2→3 的顺序搜索，输出天然就是字典序。
五、把方案存下来再输出
只输出个数不够，题目还要把每种方案具体打印出来。
加一个数组记录当前路径，再开个二维数组存所有合法方案：
#include <iostream>
using namespace std;
int n, a, cnt;
int ans; // ans 存第 i 种方案，每个方案 10 个数
void dfs(int dep, int sum) {
if (dep == 10) {
if (sum == n) {
for (int i = 0; i < 10; i++)
ans = a; // 把当前路径抄进答案数组
cnt++;
}
return;
}
for (int x = 1; x <= 3; x++) {
a = x; // ★ 关键：把选中的数记在当前路径的第 dep 个位置
dfs(dep + 1, sum + x);
// 注意：这里不用"回溯"把 a 改回来
// 因为下一轮循环会直接被新的 x 覆盖掉
}
}
关于回溯的一点说明：
有人会问：不是要在 dfs 回来后写 a = 0 吗？
这里 不用。因为下一轮循环 x 变成 2 时，会执行 a = 2 直接覆盖掉原来的 1。
每一个位置的值只由当前这一层的循环决定，互不干扰。
六、补上无解的情况
题目说：如果没有方案，第一行只输出一个 0。
http://yb.woa.com/GHCweNzeCeB
▲ 图4：天平失衡 —— 总和不够 10 或超过 30，就凑不出来，输出 0
为什么会有无解？看范围：
最小总和 = 10 × 1 = 10
最大总和 = 10 × 3 = 30
所以 $n$ 只有在 之间才有解。
题目虽然写 $n \le 10000$，但 $n = 9$ 或 $n = 100$ 时一定是 0。
好在 我们的代码天然处理了这种情况：搜完 59049 种情况，一个合法的都没有，cnt 就是 0，输出 0，符合题意，不需要特判。
七、完整代码（AC 版）
**** Hidden Message *****
请不要直接在洛谷上抄袭题解。
八、复杂度分析
时间复杂度$O(3^{10}) = O(59049)$每个节点常数极小，1 秒内轻松跑完
空间复杂度$O(10)$ 栈 + $O(\text{方案数} \times 10)$二维数组存答案，几 MB 足够
递归深度10 层非常浅，不会爆栈
九、常见错误提醒
[*]忘了关同步：方案数最多近万行，用 cin/cout 不加 ios::sync_with_stdio(false) 可能超时。
[*]输出格式错了：每行的 10 个数之间用空格隔开，末尾不能有空格。
[*]数组开小了：方案数最多 8953 种，ans 第一维开 60000 是为了留足余量，别只开成 。
[*]漏了无解情况：n 在 之外输出 0，这个其实代码自带，别画蛇添足多写特判反而写错。
十、小结
1. 把题目翻译成"10 个位置填 1/2/3，和为 n"——建模。
2. 每一层逻辑一样 → 用递归代替 10 层 for 循环——DFS。
3. 按 1→2→3 顺序搜索，天然字典序——不用排序。
4. 用数组记下当前路径，找到合法方案就抄进答案——存答案。
5. n 只在 有解，超出输出 0——边界。
十一、测试点信息、测试点生成程序
希望这篇能帮你彻底理解这道题，祝 AC！:)
这题是一道爽题
如果在复赛，想不出其他方案了
直接写「10层for循环」也是可以直接AC的选择
建议做题时，也要选择合适的方法哦~ 思路：递归 = 每层决定一种配料放几克
把 10 种配料看成 10 层决策。第 k 层选 1、2、3 克，同时记录当前总美味值 sum。
当 k == 11 时，说明 10 种配料都选完了，如果 sum == n，就保存这一组方案。
因为每次从 1 到 3 顺序尝试，所以天然按字典序得到方案。
注意
每种配料最少 1 克，10 种最少 10 克；最多 3 克，10 种最多 30 克。
所以 n < 10 或 n > 30 时直接输出 0。
先搜索并保存所有方案，最后先输出方案总数，再输出每种方案。
代码
#include <bits/stdc++.h>
using namespace std;
int n, a;
int ans;
int cnt = 0;
void dfs(int k, int sum) {
if (sum > n) return; // 剪枝：已经超过 n，不用继续
if (k == 11) {
if (sum == n) {
for (int i = 1; i <= 10; i++) {
ans = a;
}
cnt++;
}
return;
}
for (int i = 1; i <= 3; i++) {
a = i;
dfs(k + 1, sum + i);
}
}
int main() {
cin >> n;
if (n < 10 || n > 30) {
cout << 0 << endl;
return 0;
}
dfs(1, 0);
cout << cnt << endl;
for (int i = 0; i < cnt; i++) {
for (int j = 1; j <= 10; j++) {
cout << ans << " ";
}
cout << endl;
}
return 0;
}
为什么不会漏？
每个位置都试了 1、2、3，相当于把所有 10 种配料的组合都走了一遍。
只要总和等于 n，就保存下来。最多 3^10 = 59049 种，数组开 60000 够用。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 高山 发表于 2026-09-23 06:11
这题是一道爽题
如果在复赛，想不出其他方案了
直 ...
说得对，这题确实是「爽题」。
每种配料只有 1~3 克，一共 10 种，总情况只有 3^10 = 59049 种。就算写 10 层 for 循环暴力枚举，也完全能 AC。
不过要注意：
1. 输出顺序要求字典序。只要第 1 种到第 10 种配料都从 1 到 3 枚举，得到的就是字典序。
2. 第一行要先输出方案总数，再输出具体方案。所以要么先统计一遍，要么把方案存下来。
10 层 for 循环核心大概是这样：
int a, n, cnt = 0;
cin >> n;
if (n < 10 || n > 30) {
cout << 0;
return 0;
}
for (a = 1; a <= 3; a++)
for (a = 1; a <= 3; a++)
for (a = 1; a <= 3; a++)
for (a = 1; a <= 3; a++)
for (a = 1; a <= 3; a++)
for (a = 1; a <= 3; a++)
for (a = 1; a <= 3; a++)
for (a = 1; a <= 3; a++)
for (a = 1; a <= 3; a++)
for (a = 1; a <= 3; a++) {
int sum = 0;
for (int i = 1; i <= 10; i++) sum += a;
if (sum == n) cnt++;
}
cout << cnt << endl;
// 然后同样的 10 层循环再写一遍，遇到 sum == n 就输出方案
虽然能过，但写两遍 10 层循环太累，也容易漏括号。所以更推荐用递归 DFS，把「第 k 种配料」当成一层，递归到第 11 层判断，代码短、好调，还能剪枝。
总结：比赛时优先 DFS，实在不会，10 层 for 循环也能保底 AC。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 牛 {:5_106:} {:5_106:} 厉害！ {:5_106:} {:5_110:}
页:
[1]