2026-01-06

算法►回溯

子集型回溯（2026-01-06）

子集型回溯应用范围：子集/组合/切分字符串/按位选择等“枚举所有可能”的题。

基础题目

子集
电话号码字母组合
分割回文串

扩展题目

二叉树的所有路径
路径总和 II
字母大小写全排列

1. 什么是回溯？

以集合 (1,2,3) 的子集为例：我们可以选择 1，也可以“退回去”不选 1 改选 2，再选 3。
这种在构造答案的过程中回退到上一步、去探索其它分支的现象就是回溯。

回溯通常伴随递归，而不是循环：

循环适合固定层数（例如 2 层、3 层嵌套）。
但回溯题的“层数”往往未知或很深（例如字符串切分、树路径、排列组合），循环表达能力有限。
递归天然对应一棵“决策树”的深度优先遍历（DFS），更适合回溯。

2. 用“树”和“路径”理解回溯

把回溯理解成 DFS 遍历一棵决策树最直观：

每走到一个节点，我们都处于一条“根 → 当前节点”的路径上
用 path 维护这条路径
当到达满足条件的位置（通常是叶子，或某些题的节点），把 path 记录到 ans

关键点：回溯 = 递归返回 + 恢复现场

3. 恢复现场：为什么必须做？

在 DFS 过程中我们经常会：

把一个选择加入 path
递归深入
返回时必须撤销这个选择，否则 path 会“污染”后续分支

常见的两种恢复方式：

数据覆盖：适用于“固定长度答案”（常用数组保存）
回滚（removeLast）：适用于 List / StringBuilder 这种动态结构

add → dfs → removeLast
只要你“改变了状态”，回来的时候就要“撤销状态”。

4. 子集型回溯的两大思路

回溯题通常两种建模方式：

思路 A：从输入角度——“当前元素选不选”

每个输入元素对应一层决策：选 / 不选
决策树通常是二叉树
答案通常在叶子节点收集

思路 B：从答案角度——“当前位置选哪个元素”

每一层表示“答案的当前位选什么元素”
用 startIndex 控制下一层枚举起点，避免重复
答案通常在节点收集（因为走到任意节点都代表一个合法子集）

两种思路都能做 78 子集；
哪个更顺手取决于题型，有时“答案角度”的树更小，有时“选不选”更直观。

5. 画树：回溯卡住时最有效的解法

当你对“递归参数是什么、何时收集答案、怎么剪枝”不明确时：

先画出决策树
每一层代表什么？
每条边代表什么选择？
哪些节点是合法答案？

画树能直接定位：答案在哪里收集 + 哪一步需要回溯。

6. 结合题目：78 子集（两种思路）

6.1 解法 1：枚举输入元素选不选（叶子收集答案）

特点：二叉决策树；当 i == nums.length 才表示一条路径完全确定，因此在叶子收集。

void dfs(int i, int[] nums, List<Integer> path, List<List<Integer>> ans) {
    // 递归边界：输入枚举完了，path 是一种完整选择
    if (i == nums.length) {
        ans.add(new ArrayList<>(path)); // 注意要拷贝
        return;
    }

    // 1) 不选 nums[i]
    dfs(i + 1, nums, path, ans);

    // 2) 选 nums[i]
    path.add(nums[i]);
    dfs(i + 1, nums, path, ans);
    path.removeLast(); // 恢复现场
}

注意：

叶子收集：因为只有到 i==n 才能确定“每个元素选没选”
必须拷贝 path：否则 ans 里存的是同一个引用，后续回滚会影响已保存答案
恢复现场：每次 add 后都要 removeLast

6.2 解法 2：枚举第 i 个答案选哪个元素（节点收集答案）

特点：每个节点都是一个子集，因此走到节点就可记录；用 startIndex 防止重复。

void dfs(int start, int[] nums, List<List<Integer>> ans, List<Integer> path) {
    // 由于每个节点都是一个合法子集，所以直接记录当前 path
    ans.add(new ArrayList<>(path));

    // 枚举下一位选哪个元素：只能从 start 往后选，保证不出现 (2,1) 这种重复顺序
    for (int j = start; j < nums.length; j++) {
        path.add(nums[j]);
        dfs(j + 1, nums, ans, path);
        path.removeLast(); // 回滚
    }
}

你需要牢记的点：

节点收集：因为任何时刻的 path 都是一个合法子集
startIndex 是去重本质：规定递增选取顺序，避免同一组合的不同排列
这类写法也是“组合类题”通用模板（如组合总和、组合数等）

7. String.join：在回溯里怎么用？和 StringBuilder 有什么关系？

在题解中看到有人用了 String.join()，它很适合把结果“输出成字符串”：

1 2	List<String> path = List.of("a", "b", "c"); String s = String.join("-", path); // "a-b-c"

但需要注意它和 StringBuilder / StringJoiner 的定位不同：

String.join：一次性把已有的字符串集合拼起来（更像“格式化输出”）
StringBuilder：回溯过程中不断 append / delete（更像“构造过程中的状态”）
StringJoiner：更偏“带前后缀的 join”，比如 "[a,b,c]"

在回溯题中一般推荐：

构造过程：用 StringBuilder（append + deleteCharAt 回滚）
输出阶段：需要展示路径时用 String.join（更清爽）

8. 总结

模板 1（选不选，叶子收集）

参数：i
收集：i == n
结构：先不选，再选（选完要回滚）

模板 2（答案角度，节点收集）

参数：start
收集：进入 dfs 就收集
结构：for 从 start 枚举，递归 dfs(start +1)，回滚

9. 心得体会

回溯的本质是DFS 遍历决策树，path 记录当前路径，ans 收集答案。
回溯一定伴随恢复现场：add → dfs → removeLast。
子集型题最常用两种建模：
- 选不选（叶子收集）
- 选哪个（节点收集 + startIndex 去重）
思路不清楚时，画树是最高效的破局方法。
String.join 更适合输出拼接；回溯构造过程更推荐 StringBuilder 做状态并回滚。

廷风的技术博客

Java 后端开发