🔁 C++ 回溯算法教程（零基础版）

从0开始，通俗易懂讲解回溯法 + 模板 + 示例代码 + 图解风格

🧠 什么是回溯算法？

回溯算法（Backtracking） 是一种系统地尝试所有可能解的算法思想。它类似于“试错”的过程：

如果你走到了死胡同，就回头，换条路继续走。

在编程中，这种思想非常适合解决以下问题：

  • 全排列
  • 组合问题
  • 子集问题
  • N皇后问题
  • 数独求解
  • 路径搜索等

⚙️ 回溯算法的核心思想

  1. 尝试每一种可能的选择
  2. 如果当前选择导致无法得到正确解 → 回退（Backtrack）
  3. 直到找到一个可行解 或 尝试完所有路径

类比生活中的迷宫寻路：你走到岔路口就选一条路走，走不通就返回重新选。

📦 回溯算法的基本模板

void backtrack(参数) {
    if (满足结束条件) {
        记录结果;
        return;
    }

    for (选择：本层集合中的元素) {
        处理当前节点；
        backtrack(下一层);
        回溯操作（撤销刚才的选择）；
    }
}

🎯 常见回溯问题类型 & 示例

✅ 1. 全排列问题（Permutations）

🧩 题目描述：

给定一个不含重复数字的数组 nums，返回它的所有全排列。

💻 示例代码：

#include <iostream>
#include <vector>
using namespace std;

// 回溯函数
void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& res) {
    if (path.size() == nums.size()) {
        res.push_back(path);  // 找到一个完整排列
        return;
    }

    for (int i = 0; i < nums.size(); ++i) {
        if (used[i]) continue;  // 已使用过跳过

        used[i] = true;         // 标记为已使用
        path.push_back(nums[i]); // 添加当前元素

        backtrack(nums, path, used, res); // 进入下一层

        path.pop_back();        // 回溯：撤销选择
        used[i] = false;        // 撤销标记
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used(nums.size(), false);

    backtrack(nums, path, used, res);

    cout << "全排列如下：" << endl;
    for (const auto& v : res) {
        for (int num : v)
            cout << num << " ";
        cout << endl;
    }

    return 0;
}

✅ 输出：

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

✅ 2. 组合问题（Combinations）

🧩 题目描述：

给定两个整数 n 和 k，返回 1 到 n 中所有可能的 k 个数的组合。

💻 示例代码：

#include <iostream>
#include <vector>
using namespace std;

void backtrack(int n, int k, int start, vector<int>& path, vector<vector<int>>& res) {
    if (path.size() == k) {
        res.push_back(path);  // 找到一个有效组合
        return;
    }

    for (int i = start; i <= n; ++i) {
        path.push_back(i);             // 选择 i
        backtrack(n, k, i + 1, path, res); // 下一层
        path.pop_back();               // 回溯
    }
}

int main() {
    int n = 4, k = 2;
    vector<vector<int>> res;
    vector<int> path;

    backtrack(n, k, 1, path, res);

    cout << "所有组合如下：" << endl;
    for (const auto& v : res) {
        for (int num : v)
            cout << num << " ";
        cout << endl;
    }

    return 0;
}

✅ 输出：

1 2 
1 3 
1 4 
2 3 
2 4 
3 4

✅ 3. 子集问题（Subsets）

🧩 题目描述：

给定一组不含重复元素的整数数组 nums，返回它的所有子集（幂集）。

💻 示例代码：

#include <iostream>
#include <vector>
using namespace std;

void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
    res.push_back(path);  // 每次都记录路径

    for (int i = start; i < nums.size(); ++i) {
        path.push_back(nums[i]);          // 选择当前元素
        backtrack(nums, i + 1, path, res); // 下一层
        path.pop_back();                  // 回溯
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> res;
    vector<int> path;

    backtrack(nums, 0, path, res);

    cout << "所有子集如下：" << endl;
    for (const auto& v : res) {
        cout << "[ ";
        for (int num : v)
            cout << num << " ";
        cout << "]" << endl;
    }

    return 0;
}

✅ 输出：

[ ]
[ 1 ]
[ 1 2 ]
[ 1 2 3 ]
[ 1 3 ]
[ 2 ]
[ 2 3 ]
[ 3 ]

🎨 回溯算法流程图（伪代码风格）

开始
│
├─→ 是否满足结束条件？
│   └─→ 是 → 加入结果并返回
│
├─→ 否 → 枚举当前可选元素
│
├─→ 对每个选项：
│       处理该选项
│       回溯下一层
│       回溯撤销处理
│
└─→ 结束返回

🧰 回溯算法小技巧总结

技巧 说明
🔄 循环嵌套 枚举当前层的所有可能选择
📦 参数设计 包含路径、已访问状态、起始位置等信息
🧹 剪枝优化 提前判断不可能的情况，减少无效递归
🧠 状态恢复 每次递归后要恢复现场，才能尝试下一个选择

🧪 推荐练习题（适合初学者）

题号 题目名称 类型
LeetCode 46 全排列 排列类
LeetCode 77 组合 组合类
LeetCode 78 子集 子集类
LeetCode 90 子集 II 带重复元素的子集
LeetCode 51 N皇后 实战应用
LeetCode 39 组合总和 DFS+剪枝

📚 推荐学习路线图

枚举入门 👉 回溯基础 👉 全排列 👉 组合 👉 子集 👉 N皇后 👉 数独

🙋‍♂️ 如何继续学习？

如果你希望我继续扩展以下内容，请告诉我：

  • 如何用类封装回溯函数？
  • 如何加入剪枝优化提高效率？
  • 如何画出回溯过程帮助理解？
  • 如何解决带重复元素的组合/子集问题？

😊

📌 结语：
回溯算法是算法学习的重要一步，虽然看起来有点复杂，但只要你多写几个例子，就能掌握它的精髓！它是很多高级算法（如DFS、动态规划）的基础！

需要配套练习题或进阶讲解也可以随时告诉我哦 😊

3 条评论

  • @ 2025-5-19 21:59:30

    • @ 2025-5-19 21:56:16

      回溯算法是一种通过尝试所有可能的路径来寻找问题解的算法。当探索到某一步时，如果发现当前路径无法得到有效解，就“回溯”到上一步，尝试其他路径。下面是C++中回溯算法的常见模板。

      通用回溯模板

      #include <vector>
using namespace std;

vector<vector<int>> result; // 存储最终结果

void backtrack(vector<int>& path, vector<int>& choices) {
    // 终止条件：当达到决策树的叶子节点时，将当前路径加入结果集
    if (isValidSolution(path)) {
        result.push_back(path);
        return;
    }
    
    // 遍历所有可能的选择
    for (int choice : choices) {
        // 剪枝：如果当前选择不合法，跳过
        if (!isValidChoice(path, choice))
            continue;
            
        // 做选择：将当前选择加入路径
        path.push_back(choice);
        
        // 进入下一层决策树
        backtrack(path, choices);
        
        // 撤销选择：回溯到上一步
        path.pop_back();
    }
}

// 判断当前路径是否是一个有效解
bool isValidSolution(vector<int>& path) {
    // 根据具体问题实现判断逻辑
    return true;
}

// 判断当前选择是否合法
bool isValidChoice(vector<int>& path, int choice) {
    // 根据具体问题实现判断逻辑
    return true;
}

      排列问题模板

      #include <vector>
using namespace std;

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    
    backtrack(nums, path, used, result);
    return result;
}

void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, 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;
            
        // 做选择
        used[i] = true;
        path.push_back(nums[i]);
        
        // 进入下一层决策树
        backtrack(nums, path, used, result);
        
        // 撤销选择
        path.pop_back();
        used[i] = false;
    }
}

      组合问题模板

      #include <vector>
using namespace std;

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> result;
    vector<int> path;
    
    backtrack(1, n, k, path, result);
    return result;
}

void backtrack(int start, int n, int k, vector<int>& path, vector<vector<int>>& result) {
    // 当路径长度等于k时，说明找到了一个组合
    if (path.size() == k) {
        result.push_back(path);
        return;
    }
    
    // 遍历所有可能的选择
    for (int i = start; i <= n; i++) {
        // 做选择
        path.push_back(i);
        
        // 进入下一层决策树
        backtrack(i + 1, n, k, path, result);
        
        // 撤销选择
        path.pop_back();
    }
}

      子集问题模板

      #include <vector>
using namespace std;

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> path;
    
    backtrack(0, nums, path, result);
    return result;
}

void backtrack(int start, vector<int>& nums, vector<int>& path, vector<vector<int>>& result) {
    // 收集所有路径，包括空集
    result.push_back(path);
    
    // 遍历所有可能的选择
    for (int i = start; i < nums.size(); i++) {
        // 做选择
        path.push_back(nums[i]);
        
        // 进入下一层决策树
        backtrack(i + 1, nums, path, result);
        
        // 撤销选择
        path.pop_back();
    }
}

      这些模板提供了回溯算法的基本框架，实际应用中需要根据具体问题调整isValidSolution、isValidChoice函数的实现，以及路径和选择的表示方式。回溯算法通常用于解决排列、组合、子集、棋盘等问题。

      • @ 2025-5-19 21:55:19

        回溯算法是一种通过构建所有可能的候选解并逐步排除不符合条件的解来解决问题的方法。它的核心思想是尝试每一种可能的选择，如果当前选择导致无法得到正确解，则撤销该选择（即“回溯”），然后尝试其他可能的选择。以下是几种常见的回溯算法基本模板及其应用场景。

        基本模板

        1. 通用回溯模板

        这是一个比较通用的回溯算法模板，适用于大多数需要探索所有可能性的问题：

        void backtrack(参数) {
    if (满足结束条件) {
        记录结果;
        return;
    }

    for (选择：本层集合中的元素) { // 遍历当前层的所有选择
        处理当前节点；
        backtrack(路径, 选择列表); // 递归调用，进入下一层决策树
        回溯操作（撤销刚才的选择）；// 撤销选择，回到上一步的状态
    }
}

        2. 组合问题模板

        组合问题是从给定的n个元素中选出k个元素的所有可能组合。例如，从数组[1, 2, 3]中选出两个数的所有组合。

        void combineBacktrack(int n, int k, int start, vector<int>& current, vector<vector<int>>& result) {
    if (current.size() == k) {
        result.push_back(current);
        return;
    }

    for (int i = start; i <= n; ++i) {
        current.push_back(i); // 选择当前元素
        combineBacktrack(n, k, i + 1, current, result); // 进入下一层
        current.pop_back(); // 回溯，撤销选择
    }
}

        3. 排列问题模板

        排列问题是指找出一组数的所有排列方式。与组合不同的是，排列考虑顺序，而组合不考虑。

        void permuteBacktrack(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; // 如果已经使用过该数字则跳过
        used[i] = true; // 标记为已使用
        path.push_back(nums[i]); // 选择当前元素
        permuteBacktrack(nums, used, path, result); // 递归调用
        path.pop_back(); // 回溯，撤销选择
        used[i] = false; // 取消标记
    }
}

        4. 子集问题模板

        子集问题是要找出一个集合的所有子集，包括空集和它本身。

        void subsetBacktrack(vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
    result.push_back(current); // 每次进入都记录当前状态

    for (int i = start; i < nums.size(); ++i) {
        current.push_back(nums[i]); // 选择当前元素
        subsetBacktrack(nums, i + 1, current, result); // 递归调用
        current.pop_back(); // 回溯，撤销选择
    }
}

        这些模板可以根据具体问题的需求进行调整和扩展。例如，在解决N皇后问题、数独问题等时，可以基于上述模板添加特定的逻辑来处理约束条件或优化搜索过程。通过练习不同的题目类型，你可以更好地理解和掌握如何应用回溯算法解决实际问题。

        • 1
        428
        已通过
        0
        题解被赞
        1. 关于
        2. 联系我们
        3. 隐私
        4. 服务条款
        5. 版权申诉
        6. Language
        7. 兼容模式
        8. 主题
        4. 在线咨询
        5. Worker 0, 37ms
        6. Powered by Hydro v4.13.3 Community