回溯算法是一种暴力搜索方法，通过递归尝试所有可能路径并在不满足条件时回退，避免无效计算。其核心是“做选择”和“撤销选择”，常用path记录当前路径，结合选择列表与剪枝优化效率。组合问题通过起始索引防止重复，排列问题用visited数组标记已使用元素，子集问题则每步选择是否加入当前元素。C++实现中借助递归函数维护状态，典型结构包括结束条件判断、循环中的选择与回溯恢复。掌握该模式可解决多数搜索类问题，关键在于理解状态的传递与还原机制。
回溯算法本质上是一种暴力搜索方法，适用于解决组合、排列、子集等搜索类问题。它通过递归尝试所有可能的路径，并在不满足条件时及时“回退”，从而避免无效计算。C++ 中实现回溯算法的关键在于状态维护与路径记录，下面给出一个通用框架和具体应用示例。
回溯算法基本结构
回溯的核心是“做选择”和“撤销选择”。其模板如下：
void backtrack(vector<int>& path, 其他参数) {
if (满足结束条件) {
记录结果;
return;
}
for (选择 in 选择列表) {
做选择：将选择加入 path;
backtrack(path, 其他参数);
撤销选择：从 path 移除该选择;
}
}
关键点：
- path：记录当前路径的选择序列
- 选择列表：根据题目限制动态变化
- 剪枝：在循环中提前跳过不可能的情况，提升效率
组合问题（如：从 n 个数中选 k 个）
要求无序且不重复，可用起始索引控制顺序，防止重复组合。
立即学习“C++免费学习笔记（深入）”；
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> path;
function<void(int)> backtrack = [&](int start) {
if (path.size() == k) {
res.push_back(path);
return;
}
for (int i = start; i <= n; ++i) {
path.push_back(i);
backtrack(i + 1); // 下一轮从 i+1 开始，保证升序
path.pop_back();
}
};
backtrack(1);
return res;
}
排列问题（如：全排列）
元素可按任意顺序出现，需用 visited 数组标记已使用元素。
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
vector<bool> used(nums.size(), false);
function<void()> backtrack = [&]() {
if (path.size() == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (used[i]) continue;
path.push_back(nums[i]);
used[i] = true;
backtrack();
path.pop_back();
used[i] = false; // 回溯恢复状态
}
};
backtrack();
return res;
}
子集问题（每个元素选或不选）
每一步都可选择“加入”或“跳过”当前元素。
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
function<void(int)> backtrack = [&](int start) {
res.push_back(path); // 每次进入都记录，包括空集
for (int i = start; i < nums.size(); ++i) {
path.push_back(nums[i]);
backtrack(i + 1);
path.pop_back();
}
};
backtrack(0);
return res;
}
基本上就这些。掌握这个模式后，多数搜索类问题都可以套用类似结构，只需调整选择逻辑和剪枝条件即可。关键是理解递归过程中状态如何传递与还原。
