掌握C++回溯算法（从零开始的回溯法教程）

回溯算法的三大要素

1. 路径（Path）：已经做出的选择。
2. 选择列表（Choices）：当前可以做的选择。
3. 结束条件（Base Case）：到达决策树的底层，无法再做选择。

C++回溯算法模板

大多数回溯问题都可以套用以下通用模板：

void backtrack(vector<T>& path, vector<T>& choices) {    // 结束条件    if (满足结束条件) {        result.push_back(path);        return;    }    for (int i = 0; i < choices.size(); i++) {        // 做选择        path.push_back(choices[i]);                // 进入下一层决策        backtrack(path, 新的选择列表);                // 撤销选择（回溯！）        path.pop_back();    }}

实战案例：全排列问题

我们以经典的全排列问题为例：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

例如：输入 [1,2,3]，输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

这个问题完美体现了递归与回溯的思想。

C++ 实现代码

#include <iostream>#include <vector>using namespace std;void backtrack(vector<int>& nums, vector<bool>& used,               vector<int>& path, vector<vector<int>>& result) {    // 结束条件：路径长度等于原数组长度    if (path.size() == nums.size()) {        result.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(nums, used, path, result);        // 撤销选择（关键！）        path.pop_back();        used[i] = false;    }}vector<vector<int>> permute(vector<int>& nums) {    vector<vector<int>> result;    vector<int> path;    vector<bool> used(nums.size(), false);    backtrack(nums, used, path, result);    return result;}// 测试函数int main() {    vector<int> nums = {1, 2, 3};    auto res = permute(nums);    for (auto& perm : res) {        for (int x : perm) cout << x << " ";        cout << endl;    }    return 0;}

为什么需要“撤销选择”？

这是回溯算法最核心的一点！因为 path 是引用传递（为了节省空间），如果不撤销，上一层递归留下的状态会影响下一次选择。通过 pop_back() 恢复现场，才能保证每次循环都从“干净”的状态开始尝试新路径。

常见应用场景

• N皇后问题
• 数独求解
• 组合总和（Combination Sum）
• 子集生成
• 单词搜索（Word Search）

总结

通过本教程，你应该已经掌握了C++算法设计中回溯法的基本框架和实现技巧。记住：回溯 = 递归 + 选择 + 撤销。多练习经典题目，你会逐渐体会到这种“试错-回退”策略的简洁与强大。

现在，打开你的IDE，动手写一个回溯程序吧！实践是掌握C++回溯算法的最佳方式。