回溯的本质：在迷宫中寻找所有出路

一、 前言：什么是回溯算法？

💬 开篇：在前面的文章中，我们学习了二叉树的 DFS（深度优先搜索）。如果说二叉树的路径是天然存在的，那么在解决排列组合问题时，我们需要自己构建一棵状态树并对其进行 DFS。

🚀 核心思想：“试错”与“撤销”
回溯算法就像是在走迷宫。你每走到一个路口，就面临几个选择（Choice）。

1. 你先尝试走第一条路（做出选择）。
2. 顺着这条路一直走到底（递归深搜）。
3. 走到底发现没路了，或者找到了一个出口，你必须退回到上一个路口，把刚刚留在地上的标记擦掉（撤销选择/恢复现场），然后去试下一条路。这个“退回并擦除标记”的动作，就是大名鼎鼎的回溯（Backtracking）。

👍 点赞、收藏与分享：全排列和子集是回溯算法的两座大山，今天我们直接把这两座大山推平！

1.1 万能的回溯模板

在写代码之前，先把这套模板刻在脑子里。后面所有的回溯题，全都是在这个模板上缝缝补补。

void backtrack(当前状态/路径 path, 可选列表 choices) {
    // 1. 满足结束条件
    if (达到叶子节点) {
        将 path 添加到结果集 res;
        return;
    }

    // 2. 遍历所有选择
    for (int i = 0; i < choices.size(); i++) {
        // (可选) 剪枝操作：如果不合法，continue 跳过

        // 3. 做出选择
        将 choices[i] 加入 path;
        标记 choices[i] 已被使用;

        // 4. 递归进入下一层
        backtrack(path, choices);

        // 5. 撤销选择（恢复现场），极其重要！
        将 choices[i] 从 path 中移除;
        解除 choices[i] 的使用标记;
    }
}

接下来，我们直接上实战，用两道最经典的题目来印证这个模板！

---

二、 全排列：回溯的Hello World

2.1 题目描述

题目链接：46. 全排列

描述：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

2.2 超详细深度剖析

1. 状态树的构建

想象你在玩一个填空游戏，有三个空位 [ _ , _ , _ ]，你有三个数字 1, 2, 3。

• 第一个空位：你可以填 1，可以填 2，也可以填 3。
• 第二个空位：如果你第一个空填了 1，那么第二个空只能从剩下的 2, 3 里选。
• 第三个空位：如果你前两个填了 1, 2，第三个空没得选，只能填 3。

这其实就是在遍历一棵树：

ASCII 状态树图解：

                            [ ]  (空状态)
                  /          |           \
               [1]          [2]          [3]         <-- 第 1 层
             /     \       /   \        /   \
          [1,2]  [1,3]  [2,1] [2,3]  [3,1]  [3,2]    <-- 第 2 层
            |      |      |     |      |      |
        [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]   <-- 第 3 层 (达到结束条件)

2. 为什么要恢复现场？

我们来看代码执行的真实微观过程（以左边最深的一条路为例）：

1. 往 path 里加 1，变成 [1]。
2. 进入下一层，往 path 里加 2，变成 [1, 2]。
3. 进入下一层，往 path 里加 3，变成 [1, 2, 3]。
4. 长度满了，把 [1, 2, 3] 塞进结果集。准备返回上一层。

关键来了：返回到第 2 层时，如果我们要尝试把 3 换成其他数字，我们当前的 path 必须退回到 [1, 2] 的状态！如果不退回，继续加数字，path 就会变成 [1, 2, 3, 某数]，直接乱套。
并且，3 被用过的标记也要擦除，否则别人也没法用。

这就叫恢复现场！

2.3 C++ 代码实战（保姆级注释）

class Solution {
private:
    vector<vector<int>> ret; // 存放所有排列结果
    vector<int> path;        // 存放当前正在探索的路径
    bool check[7] = {false}; // 标记数组，记录哪些数字被用过了 (题目说长度最多为6)

public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);
        return ret;
    }

    void dfs(vector<int>& nums) {
        // 1. 递归出口（满足结束条件）
        // 当我们收集的数字个数等于原数组长度时，说明一个排列完成了
        if (path.size() == nums.size()) {
            ret.push_back(path); // 记录下这个排列
            return;              // 功成身退，返回上一层
        }

        // 2. 遍历所有可能的选择
        // 在这一层，我们要从 nums 里面挑一个还没用过的数字
        for (int i = 0; i < nums.size(); i++) {
            // 如果这个数字没被用过
            if (!check[i]) {
                // 3. 做出选择
                path.push_back(nums[i]); // 把数字放进路径
                check[i] = true;         // 标记为已使用，防止下层重复用

                // 4. 递归进入下一层
                // 带着当前的 path 和 check 状态，去填下一个空位
                dfs(nums);

                // 5. 撤销选择（恢复现场！！！）
                // 从下一层退回来后，我们要把刚才放进去的数字拿出来
                // 并且把它的使用标记抹掉，让它能参与别的排列
                path.pop_back();
                check[i] = false;
            }
        }
    }
};

---

三、 子集：每个元素选与不选的哲学

3.1 题目描述

题目链接：78. 子集

描述：
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。

示例：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

3.2 两种流派的深度剖析

求子集有两种非常经典的回溯视角，掌握这两种视角，你对递归树的理解将会有质的飞跃。

视角一：选与不选法（二叉树模型）

这是最符合直觉的解法。
对于数组中的每一个元素，我们只有两个选择：要它，或者 不要它。
数组长度为 $N$，就会做 $N$ 次选择，最终形成一棵高度为 $N$ 的满二叉树，叶子节点就是所有的子集（共 $2^N$ 个）。

ASCII 状态树图解 (视角一)：

当前处理 1：               [ ]
                     / (选1)  \ (不选1)
                   [1]         [ ]
当前处理 2：      /   \       /   \
(选2/不选2)   [1,2]   [1]   [2]   [ ]
当前处理 3：  /  \    /  \   / \   / \
           123 12  13  1   23 2   3  []  <-- 第3层遍历完，收集所有结果

视角二：多叉树模型（更通用的回溯写法）

我们不关注“选不选”，我们关注“下一步能选谁”。

• 刚开始是空集 []。
• 我们可以在 [] 的基础上，往后加 1，或者加 2，或者加 3。
• 如果加了 1 变成 [1]，为了避免重复，我们只能在 1 后面的元素里挑，也就是加 2 或 3。
• 注意：这棵树上的每一个节点（不只是叶子），都是一个有效的子集！ 所以我们要在刚进入递归时，就把当前状态存起来。

ASCII 状态树图解 (视角二)：

                          [ ]  (收集)
                /          |         \
(选1及其后)  [1] (收集)  [2] (收集)  [3] (收集)
             /   \         |
         [1,2]  [1,3]    [2,3]
          /     (收集)   (收集)
      [1,2,3]
      (收集)

3.3 C++ 代码实战

解法一代码：选与不选

class Solution {
private:
    vector<vector<int>> ret;
    vector<int> path;

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }

    // pos 表示当前面临抉择的是 nums[pos] 这个元素
    void dfs(vector<int>& nums, int pos) {
        // 1. 递归出口
        // 当我们对所有的元素都做完了抉择（pos == nums.size()），记录当前路径
        if (pos == nums.size()) {
            ret.push_back(path);
            return;
        }

        // 2. 选择一：我要这个元素
        path.push_back(nums[pos]); // 加进背包
        dfs(nums, pos + 1);        // 带着它去考虑下一个元素
        path.pop_back();           // 恢复现场：考虑完“要它”的情况后，把它拿出来

        // 3. 选择二：我不要这个元素
        // 现场已经干干净净，直接跳过它，去考虑下一个元素
        dfs(nums, pos + 1);
    }
};

解法二代码：多叉树遍历（推荐掌握，更普适）

class Solution {
private:
    vector<vector<int>> ret;
    vector<int> path;

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }

    // pos 表示本层循环可以从 nums 的哪个下标开始挑选
    void dfs(vector<int>& nums, int pos) {
        // 1. 记录结果：每一个到达的节点，都是一个合法的子集！
        // 所以一进来就先把它加到结果集里
        ret.push_back(path);

        // 2. 横向遍历尝试
        // 从 pos 开始挑，保证不走回头路，天然去重（不会出现选了2再回头选1）
        for (int i = pos; i < nums.size(); i++) {
            // 做出选择
            path.push_back(nums[i]);
            
            // 递归进入下一层，并且告诉下一层：你只能从 i + 1 开始挑了
            dfs(nums, i + 1);
            
            // 恢复现场：把刚刚加进来的数字拿掉，准备下一次循环尝试别的数字
            path.pop_back();
        }
    }
};

---

四、 总结：回溯心法提炼

💬 复盘：回溯其实就是“暴力穷举”的优雅形态。

1. 明确状态树的结构：在动手写代码前，先在纸上画出树的前三层，搞清楚每一层的 choices（选择列表）是什么。

2. 死磕恢复现场：只要在递归调用前对全局变量（或传引用的变量如 path）做了修改，递归调用回来后，必须一模一样地反向修改回去！

   • push_back 对应 pop_back。
   • check[i] = true 对应 check[i] = false。

3. 理解“选与不选” vs “多叉扩展”：

   • 如果是子集问题，既可以用二叉树，也可以用多叉树。
   • 如果是排列问题，通常用多叉树 + used 标记数组来实现。

下一篇，我们将进入组合、切割与带条件的排列问题。届时，我们会遇到回溯算法中最重要的高级技巧——剪枝（Pruning）。如果不想让程序在无用功上超时，千万不要错过！

👍 求三连支持：如果你觉得这种画图剥洋葱的讲法让你终于懂了什么是“恢复现场”，请一定要点个赞！我们下期见！ 👋