wehub-resource-sync
205 lines
7.0 KiB
Markdown
205 lines
7.0 KiB
Markdown
---
|
|
title: 回溯算法面试题总结：组合、排列、子集、剪枝与 Java 模板
|
|
description: 回溯算法面试题总结，讲解回溯题型识别、组合模板、排列模板、子集模板、去重剪枝、复杂度分析和 LeetCode 高频题。
|
|
category: 计算机基础
|
|
tag:
|
|
- 算法
|
|
head:
|
|
- - meta
|
|
- name: keywords
|
|
content: 回溯算法,回溯模板,组合,排列,子集,N皇后,剪枝,Java回溯,LeetCode回溯,算法面试题
|
|
---
|
|
|
|
回溯题的特点很明显：题目让你找所有方案、所有路径、所有组合，或者在一堆选择里试探。它和 DFS 很像，区别在于回溯更强调“选择 -> 递归 -> 撤销选择”。
|
|
|
|
面试里写回溯，最重要的是先说清递归函数的含义。函数含义稳了，参数、结束条件和撤销选择就不容易乱。
|
|
|
|
## 面试考察重点
|
|
|
|
- 能写组合、排列、子集三类模板。
|
|
- 能解释 `path`、`startIndex`、`used` 的作用。
|
|
- 能根据题目判断是否需要去重。
|
|
- 能做简单剪枝，避免无效搜索。
|
|
- 能说清复杂度和结果规模有关。
|
|
|
|
## 回溯题怎么想？
|
|
|
|
回溯题可以先画成一棵“选择树”。树上的每一层代表一次选择，根节点代表还没选，叶子节点代表一个完整方案。
|
|
|
|
写代码前先回答 4 个问题：
|
|
|
|
1. 路径是什么？通常是已经选择的元素，代码里叫 `path`。
|
|
2. 选择列表是什么？当前还能选哪些元素。
|
|
3. 结束条件是什么？什么时候把 `path` 放进答案。
|
|
4. 是否需要剪枝？哪些选择一定不会得到合法答案。
|
|
|
|
回溯模板里的“撤销选择”不是形式主义。因为 `path` 是复用的，当前分支试完后必须还原现场，给下一个分支使用。
|
|
|
|
## 组合模板
|
|
|
|
组合不关心顺序，通常用 `startIndex` 控制下一层从哪里开始：
|
|
|
|
```java
|
|
List<List<Integer>> combine(int n, int k) {
|
|
List<List<Integer>> ans = new ArrayList<>();
|
|
backtrack(1, n, k, new ArrayList<>(), ans);
|
|
return ans;
|
|
}
|
|
|
|
void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> ans) {
|
|
if (path.size() == k) {
|
|
ans.add(new ArrayList<>(path));
|
|
return;
|
|
}
|
|
for (int i = start; i <= n; i++) {
|
|
path.add(i);
|
|
backtrack(i + 1, n, k, path, ans);
|
|
path.remove(path.size() - 1);
|
|
}
|
|
}
|
|
```
|
|
|
|
组合问题不关心顺序，所以 `[1, 2]` 和 `[2, 1]` 是同一个答案。`start` 的作用就是保证后续只能选当前位置之后的数字，避免重复。
|
|
|
|
如果要从 `1..n` 里选 `k` 个数，还可以剪枝：
|
|
|
|
```java
|
|
for (int i = start; i <= n - (k - path.size()) + 1; i++) {
|
|
// ...
|
|
}
|
|
```
|
|
|
|
含义是：如果从 `i` 开始，剩余数字数量已经不够凑满 `k` 个，就没必要继续枚举。
|
|
|
|
## 排列模板
|
|
|
|
排列关心顺序，通常用 `used` 标记元素是否已经被选过：
|
|
|
|
```java
|
|
List<List<Integer>> permute(int[] nums) {
|
|
List<List<Integer>> ans = new ArrayList<>();
|
|
boolean[] used = new boolean[nums.length];
|
|
backtrack(nums, used, new ArrayList<>(), ans);
|
|
return ans;
|
|
}
|
|
|
|
void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
|
|
if (path.size() == nums.length) {
|
|
ans.add(new ArrayList<>(path));
|
|
return;
|
|
}
|
|
for (int i = 0; i < nums.length; i++) {
|
|
if (used[i]) {
|
|
continue;
|
|
}
|
|
used[i] = true;
|
|
path.add(nums[i]);
|
|
backtrack(nums, used, path, ans);
|
|
path.remove(path.size() - 1);
|
|
used[i] = false;
|
|
}
|
|
}
|
|
```
|
|
|
|
排列问题关心顺序，所以每一层都可以从所有数字里选，只是不能重复使用同一个数字。`used[i]` 表示 `nums[i]` 是否已经在当前路径里。
|
|
|
|
如果数组里有重复数字，排列去重要比组合更容易写错。通常先排序，然后在同一层跳过“前一个相同数字还没被使用”的情况：
|
|
|
|
```java
|
|
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
|
|
continue;
|
|
}
|
|
```
|
|
|
|
这句的作用是固定重复数字在同一层的选择顺序，避免生成重复排列。
|
|
|
|
## 子集模板
|
|
|
|
子集问题通常每个节点都是一个答案：
|
|
|
|
```java
|
|
List<List<Integer>> subsets(int[] nums) {
|
|
List<List<Integer>> ans = new ArrayList<>();
|
|
backtrack(0, nums, new ArrayList<>(), ans);
|
|
return ans;
|
|
}
|
|
|
|
void backtrack(int start, int[] nums, List<Integer> path, List<List<Integer>> ans) {
|
|
ans.add(new ArrayList<>(path));
|
|
for (int i = start; i < nums.length; i++) {
|
|
path.add(nums[i]);
|
|
backtrack(i + 1, nums, path, ans);
|
|
path.remove(path.size() - 1);
|
|
}
|
|
}
|
|
```
|
|
|
|
子集问题和组合问题很像，但它不是只在固定长度时收集答案，而是每到一个节点都收集一次。因为任何长度的路径都可以是一个子集。
|
|
|
|
如果题目要求去重，比如输入 `[1, 2, 2]`，仍然是先排序，再跳过同一层重复元素：
|
|
|
|
```java
|
|
if (i > start && nums[i] == nums[i - 1]) {
|
|
continue;
|
|
}
|
|
```
|
|
|
|
## 去重怎么做？
|
|
|
|
如果输入有重复元素，通常先排序，再根据题型选择去重策略：
|
|
|
|
- 子集、组合这类按下标向后选择的题，跳过同一层重复元素，例如 `i > start && nums[i] == nums[i - 1]`。
|
|
- 全排列这类每层都可能从头扫描的题，通常还要结合 `used[]`，避免同一个位置被重复使用。
|
|
- 去重判断要区分“同一层重复选择”和“同一路径重复使用”。前者会产生重复答案，后者可能正是题目允许的选择。
|
|
|
|
## 过程示意和边界样例
|
|
|
|
以 `n = 3, k = 2` 的组合问题为例，选择树可以简化成下面这样：
|
|
|
|
| 第一层选择 | 第二层可选 | 产生结果 |
|
|
| ---------- | ---------- | ------------------ |
|
|
| 选 1 | 2、3 | `[1, 2]`、`[1, 3]` |
|
|
| 选 2 | 3 | `[2, 3]` |
|
|
| 选 3 | 无 | 不足 2 个数，剪枝 |
|
|
|
|
回溯题建议检查这些边界：
|
|
|
|
| 输入 | 重点 |
|
|
| ------------ | ----------------------- |
|
|
| 空数组 | 子集题通常要返回 `[[]]` |
|
|
| `k = 0` | 组合题是否返回空组合 |
|
|
| 有重复元素 | 是否先排序并做同层去重 |
|
|
| 结果只有一个 | 是否正确拷贝 `path` |
|
|
|
|
常见错误写法：
|
|
|
|
```java
|
|
ans.add(path); // 错：后续 path 会继续变化
|
|
```
|
|
|
|
应该写成：
|
|
|
|
```java
|
|
ans.add(new ArrayList<>(path));
|
|
```
|
|
|
|
回溯里的 `path` 是复用对象，不拷贝就会导致答案里的列表一起被后续递归修改。
|
|
|
|
## 易错点
|
|
|
|
- 加入答案时要拷贝 `path`，不能直接放引用。
|
|
- 组合用 `startIndex`，排列用 `used`，不要混着写。
|
|
- 去重通常要先排序。
|
|
- 剪枝条件必须不影响正确答案。
|
|
- 回溯复杂度经常和结果数量相同量级，不要随手写 `O(n)`。
|
|
|
|
## 推荐练习题
|
|
|
|
- [77. 组合](https://leetcode.cn/problems/combinations/)
|
|
- [78. 子集](https://leetcode.cn/problems/subsets/)
|
|
- [46. 全排列](https://leetcode.cn/problems/permutations/)
|
|
- [39. 组合总和](https://leetcode.cn/problems/combination-sum/)
|
|
- [51. N 皇后](https://leetcode.cn/problems/n-queens/)
|
|
|
|
<!-- @include: @article-footer.snippet.md -->
|