回溯算法

回溯算法的本质是对一棵决策树的深度优先遍历。树上每个节点代表一次"选择"，从根到叶的一条路径就是一个完整方案。算法通过"做选择 → 递归 → 撤销选择"三步穷举所有路径，再用剪枝砍掉不合法的分支。只要理解了这棵决策树的形状，所有回溯题都是同一个框架的变体。

与网格 DFS 的关系：两者底层都是 DFS，但目的不同——回溯在隐式决策树上穷举方案（选择→递归→撤销选择），网格 DFS 在显式图/网格上搜索连通区域（访问→标记→扩展，不撤销标记）。网格搜索类问题见深度优先搜索专题。

前置知识

回溯框架

所有回溯题共享同一个骨架：

function backtrack(path, 选择列表) {
  if (满足结束条件) {
    收集结果;
    return;
  }

  for (const 选择 of 选择列表) {
    if (不合法) continue;  // 剪枝

    path.push(选择);          // 1. 做选择
    backtrack(path, 新选择列表); // 2. 递归进入下一层
    path.pop();               // 3. 撤销选择（回溯）
  }
}

框架是固定的，题与题之间的差异全部体现在以下三个维度的填充方式上：

维度	变化点	影响
选择列表的起点	for 从 start 开始 vs 从 0 开始	区分组合/子集与排列
递归时传入的起点	i + 1 vs i	区分元素能否重复选取
剪枝条件	跳过重复元素 / 跳过已访问元素	处理输入重复 / 排列去重

理解了这三个维度，后面所有题型的代码差异都只是在这三处做微调。

子集、组合、排列的本质区别

回溯最经典的三类问题——子集、组合、排列——直接对应上面三个维度的不同组合：

概念	定义	是否关注顺序	for 循环起点	递归传参
子集	选任意个元素	不关注	i = start	i + 1
组合	选固定个元素	不关注	i = start	i + 1
排列	选固定个元素	关注	i = 0	无需 start，用 visited

子集和组合本质相同（子集 = 不限长度的组合），它们与排列的核心区别是是否关注元素的排列顺序。不关注顺序就用 start 限制"只往后选"，关注顺序就从头遍历并用 visited 排除已选元素。

去重的统一方法论

当输入集合包含重复元素时，不论子集/组合还是排列，去重方法是一致的：

1. 先排序——让相同元素相邻。
2. 同层跳过——在同一层 for 循环中，如果当前元素与前一个相同，且前一个在本层已被回溯过，则跳过。

对于组合/子集，条件写作 i > start && nums[i] === nums[i - 1]——i > start 意味着前一个同值元素在本层已经展开并回溯完毕。

对于排列，条件写作 nums[i] === nums[i - 1] && !visited[i - 1]——!visited[i - 1] 说明前一个同值元素不是在"上层被选中"，而是在"本层被跳过"，从而避免重复。

两种写法形式不同但语义一致：保证相同值在同一个决策层只展开一次。

---

解题决策树

拿到一道回溯题
│
├─ 求子集 / 组合（不关注顺序）？
│  │
│  ├─ 元素唯一，每个只选一次？
│  │  └─ 基础框架 .......................... → 见「一」
│  │
│  ├─ 元素有重复，每个只选一次？
│  │  └─ 排序 + 同层去重 ................... → 见「二」
│  │
│  └─ 元素可重复选取？
│     └─ 递归时 start 不前进 ................ → 见「三」
│
├─ 求排列（关注顺序）？
│  │
│  ├─ 元素唯一？
│  │  └─ visited 数组标记 ................... → 见「四」
│  │
│  └─ 元素有重复？
│     └─ visited + 排序去重 ................. → 见「四」
│
├─ 切割 / 分割问题？
│  └─ 本质是组合：在切割点做选择 ............ → 见「五」
│
└─ 棋盘 / 网格放置问题？
   └─ 逐行/逐格放置 + 合法性剪枝 ........... → 见「六」

---

一、子集/组合：元素唯一，不可重复选

判断关键词：子集、组合、从 N 个中选 K 个、元素互不相同。

适用场景：集合中没有重复元素，每个元素在一个方案中最多出现一次。

这是回溯最基础的形态。for 循环从 start 开始保证不回头选，递归传 i + 1 保证每个元素只选一次。子集与组合唯一的差别是收集结果的时机——子集在每个节点都收集，组合在满足长度时才收集。

function backtrack(path: number[], start: number) {
  // 子集：每个节点都是答案
  // 组合：path.length === k 时才收集并 return
  res.push([...path]);

  for (let i = start; i < nums.length; i++) {
    path.push(nums[i]);
    backtrack(path, i + 1);
    path.pop();
  }
}

题型参考（框架微调）：

题目	在基础框架上的微调点
[78] 子集	标准框架，每次递归入口都收集当前 path。
[77] 组合	增加长度判断：path.length === k 时才收集并 return。

二、子集/组合：元素有重复，不可重复选

判断关键词：子集 II、组合总和 II、candidates 含重复值、结果不能重复。

适用场景：集合中有重复元素，每个元素按下标只能用一次，但要求结果集无重复方案。

在「一」的基础上只需加两步：排序 + 同层去重。i > start && nums[i] === nums[i - 1] 确保同一层 for 循环中不会对相同的值重复展开分支。

nums.sort((a, b) => a - b);

function backtrack(path: number[], start: number) {
  res.push([...path]);

  for (let i = start; i < nums.length; i++) {
    // 同层去重：前一个相同值已经展开过，跳过
    if (i > start && nums[i] === nums[i - 1]) continue;

    path.push(nums[i]);
    backtrack(path, i + 1);
    path.pop();
  }
}

题型参考（框架微调）：

题目	在去重框架上的微调点
[90] 子集 II	标准去重框架，每次递归都收集。
[40] 组合总和 II	增加 remain 参数；remain < 0 时剪枝，=== 0 时收集。

三、子集/组合：元素可重复选取

判断关键词：可无限选取、同一元素可多次使用、组合总和。

适用场景：集合中元素不重复，但每个元素可以被选取无限次。

与「一」相比，唯一的变化是递归时传入 i 而非 i + 1——允许下一层继续选同一个元素。

function backtrack(path: number[], start: number, remain: number) {
  if (remain === 0) { res.push([...path]); return; }
  if (remain < 0) return;

  for (let i = start; i < nums.length; i++) {
    path.push(nums[i]);
    backtrack(path, i, remain - nums[i]); // i 不变，允许重复选
    path.pop();
  }
}

题型参考（框架微调）：

题目	在可重复选框架上的微调点
[39] 组合总和	标准可重复选框架，remain === 0 时收集。

四、排列

判断关键词：全排列、排列顺序、所有排列方式。

适用场景：需要考虑元素的排列顺序，即 [1,2] 与 [2,1] 是不同方案。

排列与组合/子集的核心区别：for 循环每次都从 0 开始（任何位置都可以放任何元素），用 visited 数组标记哪些元素已被选过。

function backtrack(path: number[]) {
  if (path.length === nums.length) {
    res.push([...path]);
    return;
  }

  for (let i = 0; i < nums.length; i++) {
    if (visited[i]) continue;

    path.push(nums[i]);
    visited[i] = true;
    backtrack(path);
    path.pop();
    visited[i] = false;
  }
}

含重复元素的排列在此基础上加排序 + 同层去重。去重条件是 nums[i] === nums[i - 1] && !visited[i - 1]——前一个相同元素未被选中，说明它在本层已经展开并回溯过了，当前是重复分支。

nums.sort((a, b) => a - b);

function backtrack(path: number[]) {
  if (path.length === nums.length) {
    res.push([...path]);
    return;
  }

  for (let i = 0; i < nums.length; i++) {
    if (visited[i]) continue;
    if (i > 0 && nums[i] === nums[i - 1] && !visited[i - 1]) continue;

    path.push(nums[i]);
    visited[i] = true;
    backtrack(path);
    path.pop();
    visited[i] = false;
  }
}

题型参考（框架微调）：

题目	在排列框架上的微调点
[46] 全排列	标准排列框架，visited 标记已选元素。
[47] 全排列 II	增加排序 + !visited[i-1] 同层去重。

五、切割/分割问题

判断关键词：分割字符串、所有切割方案、回文分割、IP 地址复原。

适用场景：将字符串/数组切割成若干段，每段满足某个条件，求所有合法切法。

切割问题本质是组合问题的变形：在每个可能的切割点做选择。start 到 i 的子串是当前这一刀切出来的部分，如果这一段合法就递归切剩余部分，不合法就跳过——和组合框架的 start + i + 1 结构完全一致。

function backtrack(path: string[], start: number) {
  if (start === s.length) {
    res.push([...path]);
    return;
  }

  for (let i = start; i < s.length; i++) {
    const segment = s.substring(start, i + 1);
    if (!isValid(segment)) continue; // 剪枝：当前段不合法

    path.push(segment);
    backtrack(path, i + 1);
    path.pop();
  }
}

题型参考（框架微调）：

题目	在切割框架上的微调点
[131] 分割回文串	isValid 实现为回文判断。
[93] 复原 IP 地址	isValid 改为 IP 段合法性（0-255、无前导零），段数限制为 4。

六、棋盘/网格放置问题

判断关键词：N 皇后、数独、棋盘、逐行放置、约束满足。

适用场景：在二维网格上按规则放置元素，穷举所有合法布局或判断是否存在合法布局。

棋盘问题的回溯结构是"逐行/逐格决策"：每一行（或每一个空格）做一次选择，选择前检查合法性，不合法则剪枝。框架与前面完全一致，只是"选择列表"变成了列号/数字，"剪枝条件"变成了棋盘规则约束。

以 N 皇后为例，逐行放置，每行选一个列位置：

function backtrack(row: number) {
  if (row === n) {
    res.push(formatBoard(board));
    return;
  }

  for (let col = 0; col < n; col++) {
    if (!isValid(board, row, col)) continue; // 列、两条对角线冲突检测

    board[row][col] = 'Q';
    backtrack(row + 1);
    board[row][col] = '.';
  }
}

数独问题类似，但决策粒度更细——逐格而非逐行，每格尝试 1-9，合法性检查包含行、列、3×3 宫格三重约束。

题型参考（框架微调）：

题目	在棋盘框架上的微调点
[51] N 皇后	逐行放置，三方向冲突检测（列、两条对角线），收集所有方案。
[52] N 皇后 II	与 51 相同逻辑，只计数不收集方案。
[37] 解数独	逐格放置，行/列/宫格三重约束，找到一个解即返回。

---

七、其他经典回溯

部分题目不严格属于上面的分类，但依然遵循"选择—递归—撤销"框架，差异在于选择列表的构成和约束条件。

题目	回溯思路
[17] 电话号码的字母组合	每一位数字对应一组候选字母，逐位选择；类似组合但选择列表随层变化。
[22] 括号生成	每步选放 ( 或 )，通过剩余左右括号数量做剪枝。
[79] 单词搜索	网格上四方向 DFS + visited 标记，匹配到单词末位即收集。

---

总结

框架三维度速查

所有回溯题的差异可以归结为三个维度的选择：

维度	子集/组合	排列
for 循环起点	i = start	i = 0
递归传入的起点	i + 1（不可重复）/ i（可重复）	无需传 start
去重方式	i > start && nums[i] === nums[i-1]	visited + !visited[i-1]

解题速查表

题型	核心策略	典型题目
子集/组合（元素唯一）	基础框架，start + i+1	[78] [77]
子集/组合（含重复）	排序 + 同层跳过	[90] [40]
子集/组合（可重复选）	递归传 i 不传 i+1	[39]
排列（元素唯一）	visited 数组	[46]
排列（含重复）	visited + 排序去重	[47]
切割/分割	组合变形，切割点做选择	[131] [93]
棋盘放置	逐行/逐格 + 合法性剪枝	[51] [52] [37]