backtracking.md

title	回溯算法面试题总结：组合、排列、子集、剪枝与 Java 模板
description	回溯算法面试题总结，讲解回溯题型识别、组合模板、排列模板、子集模板、去重剪枝、复杂度分析和 LeetCode 高频题。
category	计算机基础
tag	算法
head	meta name content keywords 回溯算法,回溯模板,组合,排列,子集,N皇后,剪枝,Java回溯,LeetCode回溯,算法面试题

回溯题的特点很明显：题目让你找所有方案、所有路径、所有组合，或者在一堆选择里试探。它和 DFS 很像，区别在于回溯更强调“选择 -> 递归 -> 撤销选择”。

面试里写回溯，最重要的是先说清递归函数的含义。函数含义稳了，参数、结束条件和撤销选择就不容易乱。

面试考察重点

• 能写组合、排列、子集三类模板。
• 能解释 path、startIndex、used 的作用。
• 能根据题目判断是否需要去重。
• 能做简单剪枝，避免无效搜索。
• 能说清复杂度和结果规模有关。

回溯题怎么想？

回溯题可以先画成一棵“选择树”。树上的每一层代表一次选择，根节点代表还没选，叶子节点代表一个完整方案。

写代码前先回答 4 个问题：

1. 路径是什么？通常是已经选择的元素，代码里叫 path。
2. 选择列表是什么？当前还能选哪些元素。
3. 结束条件是什么？什么时候把 path 放进答案。
4. 是否需要剪枝？哪些选择一定不会得到合法答案。

回溯模板里的“撤销选择”不是形式主义。因为 path 是复用的，当前分支试完后必须还原现场，给下一个分支使用。

组合模板

组合不关心顺序，通常用 startIndex 控制下一层从哪里开始：

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 个数，还可以剪枝：

for (int i = start; i <= n - (k - path.size()) + 1; i++) {
    // ...
}

含义是：如果从 i 开始，剩余数字数量已经不够凑满 k 个，就没必要继续枚举。

排列模板

排列关心顺序，通常用 used 标记元素是否已经被选过：

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] 是否已经在当前路径里。

如果数组里有重复数字，排列去重要比组合更容易写错。通常先排序，然后在同一层跳过“前一个相同数字还没被使用”的情况：

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    continue;
}

这句的作用是固定重复数字在同一层的选择顺序，避免生成重复排列。

子集模板

子集问题通常每个节点都是一个答案：

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]，仍然是先排序，再跳过同一层重复元素：

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

常见错误写法：

ans.add(path); // 错：后续 path 会继续变化

应该写成：

ans.add(new ArrayList<>(path));

回溯里的 path 是复用对象，不拷贝就会导致答案里的列表一起被后续递归修改。

易错点

• 加入答案时要拷贝 path，不能直接放引用。
• 组合用 startIndex，排列用 used，不要混着写。
• 去重通常要先排序。
• 剪枝条件必须不影响正确答案。
• 回溯复杂度经常和结果数量相同量级，不要随手写 O(n)。

推荐练习题

• 77. 组合
• 78. 子集
• 46. 全排列
• 39. 组合总和
• 51. N 皇后