算法►回溯

回溯总结篇

在系统完成回溯相关题型后，本篇博客旨在对 回溯（Backtracking）这一类算法思想进行统一分析与方法论总结，帮助建立稳定的解题模型。

一、什么是回溯？

回溯不是一种具体算法，而是一种搜索思想。

从直观角度理解，回溯可以看作是「悔棋」：

  • 当前选择了一条路往下走
  • 发现这条路走不通，或者已经走完
  • 退回到上一个状态
  • 改选另一条路继续尝试

回溯与 DFS 的关系

回溯通常通过 递归 + 深度优先遍历（DFS） 实现。

  • DFS 负责：一路向下探索
  • 回溯负责：返回时撤销选择，恢复到上一个状态

如果把搜索过程看作一棵树：

  • 向子节点走 → 递归深入
  • 回到父节点 → 回溯
  • 访问兄弟节点 → 新的选择

什么是「增量构造答案」？

增量构造答案：
答案不是一开始就完整出现的，而是在搜索过程中一步步被“拼”出来的。

以集合 (1, 2, 3) 的子集问题为例：

  • 我们不会一开始就知道一个完整子集
  • 而是：
    1. 先决定：要不要 1
    2. 再决定：要不要 2
    3. 再决定：要不要 3
  • 每一次选择，都会在当前路径上 “增加一点信息”

因此：

  • 当前路径 path 始终是一个 “未完成的答案”
  • 只有当满足终止条件时，它才成为一个 完整答案

这也是剪枝能成立的根本原因：

如果在“构造过程中”已经不满足条件，就没必要继续往下走。

二、回溯三问（解题核心视角）

在写回溯代码前，几乎所有题目都可以先回答这三个问题。

以 电话号码的字母组合 为例（用 path 记录路径）：

问题一：当前在做什么？

当前这一层，我要决定什么？

  • 决定 path[i] 填什么字母

问题二：子问题是什么？

在当前选择之后，还剩下什么问题没解决？

  • 构造字符串中 索引 ≥ i 的部分

问题三：递归如何推进？

当前层和下一层的关系是什么？

  • 当前决定第 i 位
  • 递归进入第 i + 1 位

只要这三点清楚，回溯的递归结构自然就出来了

三、恢复现场（回溯的关键）

在 DFS + 回溯过程中，我们通常会经历：

  1. 做出一个选择（加入 path）
  2. 递归深入
  3. 返回时 撤销这个选择

如果不撤销，就会导致：

  • 当前路径“污染”后续分支
  • 结果错误或重复

常见的两种恢复现场方式

回撤（push + pop）

1
2
3
path.add(x);
dfs();
path.remove(path.size() - 1);

适合 path 长度不固定的情况。

覆盖（固定长度数组）

1
2
path[index] = x;
dfs(index + 1);

适合：

  • 全排列
  • 固定长度字符串构造

四、回溯的三种典型类型

回溯题目并不是杂乱无章的，大多数都可以归入以下三类。

以数组 [1, 2, 3] 为例：

子集型回溯（选 / 不选）

核心问题：

每个元素，选还是不选？

两种视角

  • 从输入视角：
    • 对每个元素做「选 / 不选」决策
    • 搜索树是 严格二叉树
    • 答案通常在叶子节点产生
  • 从答案构造视角：
    • 枚举第 i 个答案位置选哪个元素
    • 搜索树是 多叉树
    • 答案可以在每个节点产生

组合型回溯（子集 + 约束）

组合型回溯本质上是：

对子集型回溯增加“合法性约束 + 剪枝”

常见约束包括：

  • 选 k 个数
  • 和等于 target

为什么可以剪枝？

因为答案是增量构造的：

  • 如果当前路径已经：
    • 选多了
    • 和超了
    • 剩余元素不可能满足条件
  • 那么继续向下递归 一定不可能得到合法答案

可以提前返回，剪掉整棵子树。

排列型回溯（顺序不同即不同）

排列型回溯的核心特征：

  • 顺序敏感
  • [1,2] 和 [2,1] 是不同答案

与前两类的本质区别

  • 子集 / 组合：

    之前选过的元素，后面不能再选

  • 排列：

    只要当前路径没用过，就可以选

因此需要：

  • 一个 used / flag 数组
  • 表示当前路径中哪些元素已经使用过

五、统一的回溯伪代码模板

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        记录答案;
        return;
    }

    for (选择：当前层可选的所有选项) {
        做选择;
        backtracking(下一层参数);
        撤销选择; // 恢复现场
    }
}

六、心得总结

  • 回溯问题 不一定是“选或不选”

  • 但一定是 “做选择 → 走一条路 → 回退 → 换一条路”

  • 本质是：

    在状态空间中系统性地枚举所有可能解

一旦你能：

  • 明确「当前层在决定什么」
  • 明确「路径代表什么」
  • 明确「什么时候可以停、什么时候该剪」

那么回溯题目就不再是“凭感觉写代码”，而是一个高度可复用的方法论问题。