回溯

ZaynPei Lv6
  2025-10-12 22:00 2025-10-12 22:00 Created   2025-11-08 15:15:35 2025-11-08 15:15:35 Updated      3.1k Words  12 Mins

回溯算法是一种通过深度优先搜索 (DFS) 策略，在问题的解空间树中系统性地寻找所有（或部分）解的算法。它本质上是一种有组织的、避免了暴力枚举所有可能性的“试错法”。当算法在搜索过程中发现当前选择的路径无法导向一个有效的解时，它会“回溯”（即撤销上一步的选择），然后尝试另一个可行的选择。

其实是用递归解决多层嵌套循环

回溯算法如何工作：选择、探索、撤销

回溯算法的执行过程可以概括为以下三个步骤的循环：

  • 做出选择 (Choose)：在当前状态下，根据问题的规则，从所有可能的选择中挑选一个。

  • 递归探索 (Explore)：基于上一步的选择，进入下一层决策，递归地重复此过程。

  • 撤销选择 (Unchoose / Backtrack)：如果基于当前选择的后续探索最终没有找到解（或者已经找到了所有解），就必须撤销刚才的那一步选择，将状态恢复到做出选择之前的样子。

    • 这是回溯算法的精髓。撤销选择（例如，从路径列表中移除最后一个元素）是为了不影响在当前决策点的其他选择。就像走迷宫，你从死胡同退回到上一个岔路口后，才能去尝试其他的岔路。如果不撤销，之前的错误选择就会污染后续的搜索路径。

另一方面, 解决一个回溯问题，通常需要明确以下三个要素：

  • 选择列表 (Choices)：在当前状态下，你可以做出的所有选择的集合。

  • 路径 (Path)：你已经做出的一系列选择，构成了通往可能解的路径。

  • 结束条件 (Termination Condition / Goal)：判断当前路径是否已经构成一个完整解的条件。

回溯法树形结构

回溯算法的过程可以形象地表示为一棵树形结构，称为决策树 (Decision Tree) 或 回溯树 (Backtracking Tree)。在这棵树中： - 每个节点代表一个状态，包含当前已经做出的选择（路径）和剩余的可选选择（选择列表）。 - 每条边代表从一个状态到另一个状态的选择。 - 叶子节点代表一个完整的解，或者是一个无法继续探索的状态（死胡同）。 - 对于子集问题，所有节点（包括中间节点）都可能是解。

其中, 向下深入代表做出一个新选择(递归探索), 水平移动代表在同一层次上尝试不同的选择(for 循环遍历)。

回溯算法的代码模板

下面是一个典型的回溯算法的代码模板，展示了如何实现上述的选择、探索和撤销过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
result = [] // 存放最终结果
path = []   // 存放当前路径, 已经做出的选择

// backtrack 函数是核心
// choices: 当前可以做出的选择列表, 一般是这一层循环的起始点
function backtrack(choices) {
    // 步骤说明：首先判断是否满足结束条件。
    // 如果满足，说明找到了一个解，将其存入结果集并返回。
    if (满足结束条件) {
        add path to result;
        return;
    }

    // 步骤说明：遍历当前状态下的所有可选路径。
    for (选择 in choices) {
        // 如果这个选择不合法，可以进行“剪枝”操作，跳过它
        if (选择不合法) {
            continue;
        }

        // 1. 做出选择
        // 步骤说明：将当前选择添加到路径中。
        将“选择”添加到 path 中;

        // 2. 递归探索
        // 步骤说明：基于新的路径和新的选择列表，进入下一层决策树。
        backtrack(path, 新的选择列表);

        // 3. 撤销选择 (这步是回溯的关键！)
        // 步骤说明：将刚才添加的选择从路径中移除，
        // 以便下一次循环可以尝试当前决策点的其他选择。
        从 path 中撤销“选择”;
    }
}

一些踩过的坑

每次push_back之后，一定要记得pop_back撤销选择，否则会导致path不断增长，最终结果错误(可能会在一个backtrack调用中push多个值, 每个都要对应一次pop)。

一般适用于求解符合某种条件的所有解的问题，比如组合、排列、子集; 而求解什么什么最值的问题，一般用动态规划更合适。

有时候要求回溯算法返回路径树的所有节点而不仅仅是叶子节点，这时候结束条件就不是判断path是否构成完整解，而是每次进入backtrack函数时都把当前path加入结果集。 > 一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

对于排列问题, 在进入回溯函数的时候不需要传入startIndex, 但是需要在选择列表中判断当前元素是否已经被选择过(可以用一个visited数组记录); 而对于组合问题, 需要传入startIndex, 保证每次选择都是从startIndex开始，避免重复选择。

优缺点和适用场景

优点：

  • 通用性强：能够解决一大类问题，如排列、组合、子集、棋盘问题等。
  • 可以找到所有解：能够系统性地遍历整个解空间，找到问题的所有可行解。
  • 概念清晰：基于深度优先搜索，代码结构相对固定，容易理解。

缺点：

  • 时间复杂度高：在最坏情况下，需要遍历整个解空间，时间复杂度可能是指数级的（例如 O(n!) 或 O(2^n)）。
  • 效率问题：如果解空间巨大，且没有有效的剪枝 (Pruning) 策略（即提前判断某条路径肯定无效并终止探索），算法可能会非常慢。

典型应用场景:

  • 组合问题：在一个集合中找出所有满足条件的子集（例如：Combinations, Subsets）。
  • 排列问题：Permutations。
  • 棋盘问题：N皇后问题、数独求解器。
  • 路径寻找：迷宫问题、图的路径搜索。
  • 括号生成：生成所有有效的括号组合。

示例

示例1: 组合问题

问题：给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。 示例: 输入 n = 4, k = 2, 输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]

树结构如下: alt text 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> op;
    vector<int> path;

    void bt(int n, int k, int start){   // 组合问题按顺序选择, 所以需要start参数
        if(path.size()==k){
            op.emplace_back(path);
            return;
        }
        for(int i=start;i<n;i++){
            path.push_back(i+1);
            backtrace(n, k, i+1);  // 注意这里是 i+1, 保证每次选择都是从下一个元素开始
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        bt(n, k, 0);
        return op;
    }
};

示例2: 组合总和

问题: 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。这里的数字可以无限制重复被选取。 示例: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [[7],[2,2,3]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;

    void bt(vector<int>& candidates, int target, int start){
        if(accumulate(path.begin(), path.end(), 0)==target){
            ans.push_back(path);
            return;
        }

        if(accumulate(path.begin(), path.end(), 0)>target){  // 可以重复选取, 因此必须手动限制终止条件
            return;
        }

        for(int i = start;i<candidates.size();i++){
            path.push_back(candidates[i]);
            bt(candidates, target, i);  // 可以重复选择
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        bt(candidates, target, 0);
        return ans;
    }
};

示例3: 路径总和(二叉树)

问题: 给定一个二叉树和一个目标和，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。(LC 113)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> op;
    vector<int> path;
    int sum = 0;
    void bt(TreeNode* root, int targetSum){
        if(!root) return;

        sum += root->val;
        path.push_back(root->val);

        if(sum==targetSum && root->left==nullptr && root->right==nullptr){
            op.push_back(path);
        }
        
        bt(root->left, targetSum);
        bt(root->right, targetSum);
        path.pop_back();
        sum -= root->val;
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        bt(root, targetSum);
        return op;
    }
};

这是一个典型的树形回溯问题, 每次进入一个节点就把节点值加入path和sum中, 然后递归左右子树, 递归返回后撤销选择. 注意这里和之前的回溯问题不同, 这里的选择要在进入节点时做出, 而不是在for循环中选择.

示例: 复原 IP 地址

括号生成

问题: 给定一个整数 n ，生成所有由 n 对括号组成的有效括号组合。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<string> ans;
    string path;
    void bt(int n, int open, int close){
        if(path.size()==2*n){
            ans.push_back(path);
            return;
        }
        if(open<n){
            path.push_back('(');
            bt(n,open+1,close);
            path.pop_back();
        }
        //只有当已放置的左括号多于右括号时，才允许放置一个右括号。这正是“有效性”的精髓！ 一个无效的括号组合，当且仅当在某个点上，右括号的数量等于或超过了左括号的数量（例如 ) 或 ())）。
        if(close<open){
            path.push_back(')');
            bt(n,open,close+1);
            path.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        if(n==0) return vector<string>();
        bt(n,0,0);
        return ans;
    }
};
这道题的关键在于精准设置剪枝条件，即何时可以添加左括号，何时可以添加右括号。

我们需要理解有效括号组合的性质：在任何前缀中，左括号的数量都必须大于或等于右括号的数量。因此，在生成括号组合时，我们只能在满足这一条件的情况下添加右括号。

网格图回溯

网格图回溯问题通常涉及在一个二维网格中寻找路径或组合，这一题型的特点是在遍历每一层的选择时，选择列表是二维的（即行和列）, 并且套路写法更像纯粹的DFS而非上述模版。

单词搜索: 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。(LC 79)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <vector>
#include <string>

class Solution {
private:
    int m, n; // 矩阵的行数和列数

    /**
     * @brief 深度优先搜索 (DFS) 辅助函数
     * @param board 网格
     * @param word 目标单词
     * @param i 当前行索引
     * @param j 当前列索引
     * @param k 当前匹配到 word 的第 k 个字符
     * @return 是否找到路径
     */
    bool dfs(std::vector<std::vector<char>>& board, const std::string& word, int i, int j, int k) {
        
        // 1. 终止条件：越界或字符不匹配
        // 解释：如果 (i, j) 超出边界，或者当前格的字符不等于我们要找的 word[k]
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {
            return false;
        }

        // 2. 成功条件：匹配且到达 word 末尾
        // 解释：如果字符匹配，并且 k 已经是最后一个字符，说明 word 已找完
        if (k == word.length() - 1) {
            return true;
        }

        // 3. 标记（防止重复使用）
        // 解释：暂时将当前格修改为特殊字符，表示“已访问”
        char temp = board[i][j];
        board[i][j] = '#'; 

        // 4. 递归搜索（四个方向）
        // 解释：向 (i, j) 的上、下、左、右四个方向递归搜索 word[k+1]
        bool found = dfs(board, word, i + 1, j, k + 1) ||  // 向下
                     dfs(board, word, i - 1, j, k + 1) ||  // 向上
                     dfs(board, word, i, j + 1, k + 1) ||  // 向右
                     dfs(board, word, i, j - 1, k + 1);   // 向左

        // 5. 回溯（撤销标记）
        // 解释：无论是否找到，都必须将当前格恢复原状，
        //      以便其他起始点的搜索路径可以继续使用此格。
        board[i][j] = temp;

        return found;
    }

public:
    bool exist(std::vector<std::vector<char>>& board, std::string word) {
        if (board.empty()) return false;
        
        m = board.size();
        n = board[0].size();
        
        // 解释：遍历网格中的每一个单元格，将其作为 DFS 的起点
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 尝试从 (i, j) 开始匹配 word 的第一个字符 (k=0)
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        
        // 解释：如果所有起点都尝试失败，则返回 false
        return false;
    }
};
On this page
回溯
  1. 回溯算法如何工作：选择、探索、撤销
  2. 回溯法树形结构
  3. 回溯算法的代码模板
  4. 一些踩过的坑
  5. 优缺点和适用场景
  6. 示例
    1. 示例1: 组合问题
    2. 示例2: 组合总和
    3. 示例3: 路径总和(二叉树)
  7. 示例: 复原 IP 地址
  8. 括号生成
  9. 网格图回溯