回溯题的特点很明显：题目让你找所有方案、所有路径、所有组合，或者在一堆选择里试探。它和 DFS 很像，区别在于回溯更强调“选择 -> 递归 -> 撤销选择”。
面试里写回溯，最重要的是先说清递归函数的含义。函数含义稳了，参数、结束条件和撤销选择就不容易乱。
面试考察重点
能写组合、排列、子集三类模板。
能解释 path、startIndex、used 的作用。
pathstartIndexused能根据题目判断是否需要去重。
能做简单剪枝，避免无效搜索。
能说清复杂度和结果规模有关。
回溯题怎么想？
回溯题可以先画成一棵“选择树”。树上的每一层代表一次选择，根节点代表还没选，叶子节点代表一个完整方案。
写代码前先回答 4 个问题：
路径是什么？通常是已经选择的元素，代码里叫 path。
path选择列表是什么？当前还能选哪些元素。
结束条件是什么？什么时候把 path 放进答案。
path是否需要剪枝？哪些选择一定不会得到合法答案。
回溯模板里的“撤销选择”不是形式主义。因为 path 是复用的，当前分支试完后必须还原现场，给下一个分支使用。
path组合模板
组合不关心顺序，通常用 startIndex 控制下一层从哪里开始：
startIndexList<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);
}
}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, 2][2, 1]start如果要从 1..n 里选 k 个数，还可以剪枝：
1..nkfor (int i = start; i <= n - (k - path.size()) + 1; i++) {
// ...
}for (int i = start; i <= n - (k - path.size()) + 1; i++) {
// ...
}含义是：如果从 i 开始，剩余数字数量已经不够凑满 k 个，就没必要继续枚举。
ik排列模板
排列关心顺序，通常用 used 标记元素是否已经被选过：
usedList<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;
}
}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] 是否已经在当前路径里。
used[i]nums[i]如果数组里有重复数字，排列去重要比组合更容易写错。通常先排序，然后在同一层跳过“前一个相同数字还没被使用”的情况：
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}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);
}
}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]，仍然是先排序，再跳过同一层重复元素：
[1, 2, 2]if (i > start && nums[i] == nums[i - 1]) {
continue;
}if (i > start && nums[i] == nums[i - 1]) {
continue;
}去重怎么做？
如果输入有重复元素，通常先排序，再根据题型选择去重策略：
子集、组合这类按下标向后选择的题，跳过同一层重复元素，例如 i > start && nums[i] == nums[i - 1]。
i > start && nums[i] == nums[i - 1]全排列这类每层都可能从头扫描的题，通常还要结合 used[]，避免同一个位置被重复使用。
used[]去重判断要区分“同一层重复选择”和“同一路径重复使用”。前者会产生重复答案，后者可能正是题目允许的选择。
过程示意和边界样例
以 n = 3, k = 2 的组合问题为例，选择树可以简化成下面这样：
n = 3, k = 2第一层选择第二层可选产生结果选 12、3[1, 2]、[1, 3]选 23[2, 3]选 3无不足 2 个数，剪枝
第一层选择第二层可选产生结果
第一层选择
第二层可选
产生结果
选 12、3[1, 2]、[1, 3]
选 1
2、3
[1, 2]、[1, 3]
[1, 2][1, 3]选 23[2, 3]
选 2
3
[2, 3]
[2, 3]选 3无不足 2 个数，剪枝
选 3
无
不足 2 个数，剪枝
回溯题建议检查这些边界：
输入重点空数组子集题通常要返回 [[]]k = 0组合题是否返回空组合有重复元素是否先排序并做同层去重结果只有一个是否正确拷贝 path
输入重点
输入
重点
空数组子集题通常要返回 [[]]
空数组
子集题通常要返回 [[]]
[[]]k = 0组合题是否返回空组合
k = 0
k = 0组合题是否返回空组合
有重复元素是否先排序并做同层去重
有重复元素
是否先排序并做同层去重
结果只有一个是否正确拷贝 path
结果只有一个
是否正确拷贝 path
path常见错误写法：
ans.add(path); // 错：后续 path 会继续变化ans.add(path); // 错：后续 path 会继续变化应该写成：
ans.add(new ArrayList<>(path));ans.add(new ArrayList<>(path));回溯里的 path 是复用对象，不拷贝就会导致答案里的列表一起被后续递归修改。
path易错点
加入答案时要拷贝 path，不能直接放引用。
path组合用 startIndex，排列用 used，不要混着写。
startIndexused去重通常要先排序。
剪枝条件必须不影响正确答案。
回溯复杂度经常和结果数量相同量级，不要随手写 O(n)。
O(n)推荐练习题
- 组合
- 子集
- 全排列
- 组合总和
- N 皇后
写在最后
如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。
JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。
如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。