引言

回溯算法（Backtracking）是一种通过探索所有可能的候选解来找出所有解的算法。当探索到某一步时，发现原先的选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为"回溯点"。

回溯算法的本质：穷举所有可能，然后选出我们想要的答案。

适用场景：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 棋盘问题：N皇后，数独等等

什么是回溯算法

形象化理解

想象你在一个迷宫中寻找出口：

1
2
3
4
5
入口 → 岔路1 → 岔路2 → 死路 ✗
     ↓
     回退到岔路2
     ↓
     岔路2 → 岔路3 → 出口 ✓

这就是回溯：尝试 → 失败 → 回退 → 再尝试

决策树可视化

回溯算法可以抽象为决策树的遍历过程：

graph TD
    A[开始] --> B[选择1]
    A --> C[选择2]
    A --> D[选择3]
    B --> E[选择1.1]
    B --> F[选择1.2]
    C --> G[选择2.1]
    C --> H[选择2.2]
    
    style E fill:#90EE90
    style H fill:#90EE90
    style F fill:#FFB6C1
    style G fill:#FFB6C1
  • 绿色节点：满足条件的解
  • 粉色节点：不满足条件，需要回溯

回溯框架模板

通用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        result.push_back(路径);
        return;
    }
    
    for (选择 : 选择列表) {
        if (不满足条件) continue;  // 剪枝
        
        做选择;
        backtrack(路径, 选择列表);  // 递归
        撤销选择;  // 回溯
    }
}

三要素

  1. 路径（Path）：已经做出的选择
  2. 选择列表（Choices）：当前可以做的选择
  3. 结束条件（End Condition）：到达决策树底层，无法再做选择的条件
graph LR
    A[开始] --> B{满足结束条件?}
    B -->|是| C[保存结果]
    B -->|否| D[遍历选择列表]
    D --> E{是否有效?}
    E -->|否| F[剪枝跳过]
    E -->|是| G[做选择]
    G --> H[递归调用]
    H --> I[撤销选择]
    I --> D
    F --> D
    C --> J[返回]
    I --> K{还有选择?}
    K -->|是| D
    K -->|否| J

核心思想

回溯三步曲

  1. 做选择：将当前元素加入路径
  2. 递归：基于当前选择继续探索
  3. 撤销选择：将当前元素从路径中移除，尝试其他选择
1
2
3
4
// 伪代码示例
path.push_back(choice);      // 1. 做选择
backtrack(path, choices);    // 2. 递归
path.pop_back();             // 3. 撤销选择

关键特性

  • 时间换空间：通过回溯避免存储所有中间状态
  • 深度优先搜索（DFS）：本质上是DFS的一种实现
  • 剪枝优化：提前排除不可能的分支，提高效率

经典问题详解

1. 全排列问题

LeetCode 46: 给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

示例：

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

决策树

1
2
3
4
5
6
7
                 []
       /          |          \
     [1]         [2]         [3]
    /   \       /   \       /   \
 [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
   |     |     |     |     |     |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void permuteBacktrack(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;  // 剪枝：已使用的元素跳过
        
        // 做选择
        path.push_back(nums[i]);
        used[i] = true;
        
        // 递归
        permuteBacktrack(nums, path, used, result);
        
        // 撤销选择
        path.pop_back();
        used[i] = false;
    }
}

执行过程示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输入: [1, 2, 3]

步骤1: path=[], 选择1
       path=[1], used=[T,F,F]

步骤2: path=[1], 选择2
       path=[1,2], used=[T,T,F]

步骤3: path=[1,2], 选择3
       path=[1,2,3], used=[T,T,T]
       ✓ 找到一个解！

步骤4: 回溯，撤销3
       path=[1,2], used=[T,T,F]

步骤5: 回溯，撤销2
       path=[1], used=[T,F,F]

步骤6: path=[1], 选择3
       path=[1,3], used=[T,F,T]
       ... (继续)

时间复杂度：O(n × n!)
空间复杂度：O(n)

2. N皇后问题

LeetCode 51: 在 n×n 的棋盘上放置 n 个皇后，使得它们不能相互攻击。

规则：皇后可以攻击同一行、同一列、同一对角线上的棋子。

可视化

1
2
3
4
5
6
4皇后的一个解：

. Q . .     行0
. . . Q     行1
Q . . .     行2
. . Q .     行3

决策树

graph TD
    A[行0: 选择列] --> B[列0]
    A --> C[列1]
    A --> D[列2]
    A --> E[列3]
    
    C --> F[行1: 列3]
    F --> G[行2: 列1]
    G --> H[行3: 列2 ✓]
    
    B --> I[行1: 检查...✗]
    D --> J[行1: 检查...✗]

实现

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
void nQueensBacktrack(vector<string>& board, int row, 
                      vector<vector<string>>& result) {
    // 终止条件：所有行都放置了皇后
    if (row == board.size()) {
        result.push_back(board);
        return;
    }
    
    int n = board[row].size();
    for (int col = 0; col < n; ++col) {
        if (!isValidQueen(board, row, col)) {
            continue;  // 剪枝：不合法位置
        }
        
        // 做选择
        board[row][col] = 'Q';
        
        // 递归
        nQueensBacktrack(board, row + 1, result);
        
        // 撤销选择
        board[row][col] = '.';
    }
}

bool isValidQueen(vector<string>& board, int row, int col) {
    int n = board.size();
    
    // 检查列
    for (int i = 0; i < row; ++i) {
        if (board[i][col] == 'Q') return false;
    }
    
    // 检查左上对角线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
        if (board[i][j] == 'Q') return false;
    }
    
    // 检查右上对角线
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
        if (board[i][j] == 'Q') return false;
    }
    
    return true;
}

时间复杂度：O(n!)
空间复杂度：O(n²)

3. 组合总和

LeetCode 39: 给定一个无重复元素的数组 candidates 和一个目标数 target，找出所有可以使数字和为 target 的组合。

示例：

1
2
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

决策树

1
2
3
4
5
6
7
                        []
         /       |        |        \
       [2]      [3]      [6]      [7]✓
      / | \     / \       |
  [2,2] ...  [3,3] ...  [6,?]
   / \
[2,2,2] [2,2,3]✓

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void combinationBacktrack(vector<int>& candidates, int target, int start,
                          vector<int>& path, vector<vector<int>>& result) {
    // 终止条件
    if (target == 0) {
        result.push_back(path);
        return;
    }
    
    for (int i = start; i < candidates.size(); ++i) {
        if (candidates[i] > target) break;  // 剪枝：超过目标
        
        // 做选择
        path.push_back(candidates[i]);
        
        // 递归（可重复使用，所以传入 i）
        combinationBacktrack(candidates, target - candidates[i], i, path, result);
        
        // 撤销选择
        path.pop_back();
    }
}

关键点：

  • 可以重复使用同一元素，所以递归时传入 i 而不是 i+1
  • 排序后可以提前剪枝

4. 子集问题

LeetCode 78: 给定一个整数数组 nums，返回该数组所有可能的子集。

示例：

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

决策树

1
2
3
4
5
6
7
                 []✓
       /          |          \
     [1]✓        [2]✓        [3]✓
    /   \          \
 [1,2]✓ [1,3]✓   [2,3]✓
   |
[1,2,3]✓

关键：每个节点都是一个有效子集！

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void subsetsBacktrack(vector<int>& nums, int start,
                      vector<int>& path, vector<vector<int>>& result) {
    // 每个节点都是一个子集
    result.push_back(path);
    
    for (int i = start; i < nums.size(); ++i) {
        // 做选择
        path.push_back(nums[i]);
        
        // 递归
        subsetsBacktrack(nums, i + 1, path, result);
        
        // 撤销选择
        path.pop_back();
    }
}

时间复杂度：O(n × 2ⁿ)
空间复杂度：O(n)

5. 括号生成

LeetCode 22: 生成所有由 n 对括号组成的有效组合。

示例：

1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

约束条件

  1. 左括号数量 ≤ n
  2. 右括号数量 ≤ 左括号数量

决策树

1
2
3
4
5
6
7
                        ""
              /                    \
            "("                    ❌ ")" (违反规则2)
       /         \
    "(("        "()"
   /   \       /   \
"((("  "(()" "()"  "())"❌

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void parenthesisBacktrack(int n, int left, int right,
                          string& path, vector<string>& result) {
    // 终止条件
    if (path.size() == 2 * n) {
        result.push_back(path);
        return;
    }
    
    // 添加左括号
    if (left < n) {
        path.push_back('(');
        parenthesisBacktrack(n, left + 1, right, path, result);
        path.pop_back();
    }
    
    // 添加右括号（剪枝）
    if (right < left) {
        path.push_back(')');
        parenthesisBacktrack(n, left, right + 1, path, result);
        path.pop_back();
    }
}

时间复杂度：O(4ⁿ / √n)（卡特兰数）
空间复杂度：O(n)

剪枝优化技巧

剪枝是提高回溯算法效率的关键！

1. 提前终止

1
2
3
if (当前状态已经不可能产生有效解) {
    return;  // 直接返回，不继续递归
}

示例：组合总和中，如果当前和已经超过目标值

1
if (candidates[i] > target) break;  // 剪枝

2. 排序优化

先排序，可以更早地剪枝

1
sort(candidates.begin(), candidates.end());

3. 避免重复

使用 used 数组或 start 索引避免重复计算

1
2
3
4
5
// 全排列：used数组
if (used[i]) continue;

// 组合问题：start索引
for (int i = start; i < nums.size(); ++i)

4. 对称性剪枝

利用问题的对称性减少搜索空间

1
2
// N皇后：只搜索一半，另一半通过对称获得
if (row == 0 && col > n / 2) break;

剪枝效果对比

graph LR
    A[无剪枝] -->|搜索空间| B[10000节点]
    C[有剪枝] -->|搜索空间| D[100节点]
    
    style B fill:#FFB6C1
    style D fill:#90EE90

复杂度分析

时间复杂度

回溯算法的时间复杂度通常取决于：

  1. 决策树的深度：递归的层数
  2. 每层的选择数量：for循环的次数
问题 时间复杂度 说明
全排列 O(n × n!) n层，每层最多n个选择
N皇后 O(n!) 每行选择递减
组合 O(2ⁿ) 每个元素选或不选
子集 O(n × 2ⁿ) 2ⁿ个子集，复制需要O(n)

空间复杂度

主要考虑：

  1. 递归栈深度：O(深度)
  2. 路径存储：O(路径长度)

通常为 O(n) 或 O(树的高度)

常见LeetCode题目

入门级

中级

高级

回溯 vs DFS vs BFS

对比表

特性 回溯 DFS BFS
本质 带剪枝的DFS 深度优先搜索 广度优先搜索
数据结构 递归栈 栈/递归 队列
路径记录 显式维护 可选 可选
空间复杂度 O(h) O(h) O(w)
应用场景 所有解 单个解 最短路径

h = 树的高度, w = 树的宽度

总结

核心要点

  1. 回溯 = 穷举 + 剪枝
  2. 三要素：路径、选择列表、结束条件
  3. 三步曲：做选择 → 递归 → 撤销选择
  4. 优化关键：剪枝！剪枝！剪枝！

经典模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void backtrack(参数) {
    if (终止条件) {
        存储结果;
        return;
    }
    
    for (选择 : 选择列表) {
        if (剪枝条件) continue;
        
        做选择;
        backtrack(新参数);
        撤销选择;
    }
}

性能优化 Tips

  1. 排序预处理：便于剪枝
  2. 使用引用传参：减少复制开销
  3. 位运算优化 used 数组：节省空间
  4. 记忆化搜索：避免重复计算子问题

回溯算法是解决复杂搜索问题的利器。虽然时间复杂度较高，但通过巧妙的剪枝优化，可以在实际应用中取得很好的效果。掌握回溯算法，你将拥有解决大部分组合、排列、搜索类问题的能力！

推荐阅读：