C++ 深度优先搜索 (DFS) 回溯算法
问题描述
来源：洛谷 P2089 烤鸡
有 10 种配料，每种配料可以放 1 到 3 克。任意烤鸡的美味程度为所有配料质量之和。 给定一个美味程度 n，输出这 10 种配料的所有搭配方案。
解题思路
本题的核心是枚举所有可能的配料组合，同时满足「累加和=n」「配料数=10」两个严格约束，属于典型的组合枚举 + 约束剪枝问题。这类问题最经典、最高效的解法是 DFS(深度优先搜索)+回溯算法。
DFS 负责递归枚举每一步选择的配料美味值 (1/2/3)，回溯负责在递归结束后「撤销选择」，恢复现场，从而枚举所有可能性。
代码实现
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int n, ans = 0;
string s;
vector<string> v;
// val：当前累计的美味程度总和
// cou：当前已选择的配料数量
void dfs(int val, int cou) {
// 递归终止条件 1：找到合法方案 → 记录答案 + 方案
if (val == n && cou == 10) {
v.push_back(s); // 将合法的配料组合存入 vector 容器
ans++; // 合法方案数 +1
return;
}
// 递归终止条件 2：剪枝（无效路径，直接返回）
if (val > n || cou >= 10) {
return;
}
// 枚举当前步的所有选择：配料美味值只能是 1、2、3
for (int i = 1; i <= 3; i++) {
// 1. 做出选择：拼接当前配料值到方案字符串，先加空格，再加数字字符
s.push_back(' ');
s.push_back('0' + i);
// 2. 递归深入：累加美味值、配料数 +1，进入下一层选择
dfs(val + i, cou + 1);
// 3. 回溯撤销选择：删除刚拼接的内容，恢复字符串原状
s.pop_back();
s.pop_back();
}
}
int main() {
cin >> n;
// 初始化第一层选择
for (int i = 1; i <= 3; i++) {
s.push_back('0' + i); // 第一个配料直接存数字，不加空格
dfs(i, 1); // 初始：美味值=i，配料数=1
s.clear(); // 清空方案字符串，为下一个初始选择做准备
}
// 输出方案的总数量
cout << ans << endl;
// 遍历 vector 容器，输出每一种方案
for (string str : v) {
cout << str << endl;
}
return 0;
}
核心原理
1. 全局变量定义与作用
n：接收输入的目标美味值；ans：统计满足条件的合法方案总数，初始值为 0；string s：核心临时容器，用于拼接每一条配料组合的字符串（如1 1 1 1 1 1 1 1 1 2），拼接与删除都在这个字符串上完成；vector<string> v：结果存储容器，每找到一条合法方案，就将拼接好的字符串存入 vector，最终统一遍历输出所有方案。
2. DFS 函数的核心逻辑：递归 + 终止 + 剪枝
DFS 函数是整个程序的灵魂，函数定义 void dfs(int val, int cou) 中，两个参数的含义：
val：路径和，表示当前已经选择的所有配料的美味程度累加和；cou：路径长度，表示当前已经选择的配料的总数量。
递归的两个终止条件
递归的本质是「自己调用自己」，必须有明确的终止条件，否则会无限递归导致程序崩溃，本题包含合法终止和非法终止（剪枝） 两种：
// 合法终止：美味和刚好等于 n，且配料数刚好等于 10 → 记录答案
if (val == n && cou == 10) {
v.push_back(s);
ans++;
return;
}
// 非法终止（剪枝）：美味和超过 n 或 配料数达到 10 → 此路径无意义，直接返回
if (val > n || cou >= 10) {
return;
}
剪枝的意义：提前砍掉不可能满足条件的路径，比如配料数已经到 10 了但和不够 n、和已经超过 n 了但配料数没到 10，这些路径不需要继续递归，能大幅减少程序运行时间，这也是 DFS 比纯暴力枚举高效的核心原因。
3. 核心操作：「做选择 → 递归 → 回溯撤销选择」
这是 DFS 回溯算法的万能模板，大部分的组合、排列、子集类问题，都遵循这个模板，也是本题的核心代码段：
for (int i = 1; i <= 3; i++) {
// 第一步：做选择 → 把当前选择的配料值拼接到字符串 s 中
s.push_back(' ');
s.push_back('0' + i);
// 第二步：递归 → 进入下一层选择，更新累加和、配料数
dfs(val + i, cou + 1);
// 第三步：回溯 → 撤销刚才的选择，恢复 s 的原状
s.pop_back();
s.pop_back();
}
细节说明
- 为什么用
s.push_back('0'+i)拼接数字？ 先拼接空格' '再拼接数字，是为了让最终的方案字符串中，配料之间用空格分隔，格式更整洁。 - 为什么一定要「回溯」？什么是回溯？
回溯的本质就是「原路返回，恢复现场」。当我们选择了配料
i并递归到下一层后，递归结束时，必须把刚才拼接到s中的空格和数字删除，这样才能保证回到当前层时，字符串s的状态和选择前一致，才能继续枚举下一个配料值。
