回溯算法通用模板：全排列、子集、N皇后一套代码搞定
2026/4/30大约 9 分钟
回溯算法通用模板：全排列、子集、N皇后一套代码搞定
适读人群：算法基础薄弱、面试频繁卡在回溯题的Java开发 | 阅读时长：约16分钟 | 文章类型：算法框架+题型覆盖
开篇故事
有个候选人小许，来面试时算法部分比较薄弱，他自己也知道，提前刷了两周力扣。面试时我出了一道组合问题，他想了五分钟，说：这是回溯对吧，但我不太会写，之前背了模板又忘了。
我说：回溯不是需要背的模板，它是一种思维方式。你把回溯的思维理解了，代码自然就能写出来。
他说：什么思维方式？
我说：三步走。第一步：做选择（把一个可能的选项加入当前路径）。第二步：递归（继续往深处走，探索以这个选择开头的所有可能）。第三步：撤销选择（回到上一步，尝试其他选项）。
所有的回溯题，结构都是这三步，区别只在于"选项是什么""何时结束""如何剪枝"。
他听完想了一会儿，说：这...确实不需要背，逻辑很清楚。
然后我们一起在白板上写了全排列，15分钟，他独立完成了。
今天我把这套框架完整写出来，顺带把高频的回溯题型全覆盖。
一、回溯的通用代码框架
void backtrack(路径, 选择列表) {
if (满足结束条件) {
result.add(路径的副本);
return;
}
for (选择 in 选择列表) {
// 剪枝：如果这个选择不可行，跳过
做选择; // 修改状态（路径和选择列表）
backtrack(...); // 递归
撤销选择; // 恢复状态
}
}这个框架适用于所有回溯题，差别只在于：
- 选择列表怎么定义：全部元素？剩余元素？某个范围内的元素？
- 结束条件是什么：路径长度=n？路径和=target？
- 如何剪枝：去重？已用的不再用？超过阈值就停？
二、完整代码实现
package com.laozhang.backtrack;
import java.util.*;
/**
* 回溯算法通用框架与经典题目实现
* 覆盖：全排列、子集、组合、N皇后
* 每道题都体现同一套三步框架：做选择→递归→撤销选择
*/
public class BacktrackSolutions {
// ==================== 全排列（LeetCode 46）====================
/**
* 全排列：给定不含重复数字的数组，返回所有可能的全排列
*
* 选择列表：所有未使用的元素
* 结束条件：路径长度 = nums.length
* 不需要去重（题目保证无重复元素）
*/
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length]; // 标记元素是否已在路径中
backtrackPermute(nums, used, new ArrayList<>(), result);
return result;
}
private static void backtrackPermute(int[] nums, boolean[] used,
List<Integer> path, List<List<Integer>> result) {
// 结束条件：路径长度等于数组长度
if (path.size() == nums.length) {
result.add(new ArrayList<>(path)); // 注意：要复制一份！path是引用
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // 已使用的元素跳过
// 做选择
path.add(nums[i]);
used[i] = true;
// 递归
backtrackPermute(nums, used, path, result);
// 撤销选择
path.remove(path.size() - 1);
used[i] = false;
}
}
/**
* 全排列II：包含重复元素，结果不含重复排列（LeetCode 47）
*
* 去重技巧：排序后，如果当前元素和前一个元素相同，且前一个元素未被使用，跳过
* 为什么是"前一个未被使用"而不是"前一个已被使用"？
* 树层去重：同一树层（同一for循环）不允许用重复元素
* used[i-1]==false 说明nums[i-1]在本树层被用过然后撤销了，所以nums[i]和nums[i-1]值相同时，
* nums[i]就是重复选择，跳过
*/
public static List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // 排序是去重的前提！
boolean[] used = new boolean[nums.length];
backtrackPermuteUnique(nums, used, new ArrayList<>(), result);
return result;
}
private static void backtrackPermuteUnique(int[] nums, boolean[] used,
List<Integer> path, List<List<Integer>> result) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
// 去重：同层不允许用值相同的元素
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
path.add(nums[i]);
used[i] = true;
backtrackPermuteUnique(nums, used, path, result);
path.remove(path.size() - 1);
used[i] = false;
}
}
// ==================== 子集（LeetCode 78）====================
/**
* 子集：给定不含重复元素的整数数组，返回所有可能的子集
*
* 和全排列的区别：
* 1. 每个节点都是一个子集（不只是叶子节点才收集）
* 2. 每次递归从start开始，避免重复（[1,2]和[2,1]是同一子集）
* 3. 没有显式的结束条件（for循环自然终止时就返回）
*/
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrackSubsets(nums, 0, new ArrayList<>(), result);
return result;
}
private static void backtrackSubsets(int[] nums, int start,
List<Integer> path, List<List<Integer>> result) {
result.add(new ArrayList<>(path)); // 每个节点都是一个合法子集
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrackSubsets(nums, i + 1, path, result); // 从i+1开始，不重复选
path.remove(path.size() - 1);
}
}
// ==================== 组合总和（LeetCode 39）====================
/**
* 组合总和：candidates中的数字可以重复使用，找所有和=target的组合
* 完全背包的回溯版本
*/
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates); // 排序便于剪枝
backtrackCombination(candidates, 0, target, new ArrayList<>(), result);
return result;
}
private static void backtrackCombination(int[] candidates, int start, int remaining,
List<Integer> path, List<List<Integer>> result) {
if (remaining == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
// 剪枝：已排序，如果当前元素大于remaining，后面的更大，全可跳过
if (candidates[i] > remaining) break;
path.add(candidates[i]);
backtrackCombination(candidates, i, remaining - candidates[i], path, result); // i不+1，可重复用
path.remove(path.size() - 1);
}
}
// ==================== N皇后（LeetCode 51）====================
/**
* N皇后：在N×N棋盘放N个皇后，任意两个皇后不能同行/同列/同对角线
*
* 回溯框架套用：
* - 逐行放皇后（路径=已放置的皇后位置）
* - 选择列表=当前行的每个列
* - 合法性检查：不与已放皇后冲突
* - 结束条件：成功放了N行
*/
public static List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
int[] queens = new int[n]; // queens[row] = 该行皇后所在的列，-1表示未放置
Arrays.fill(queens, -1);
// 用三个集合快速判断列/主对角线/副对角线是否已有皇后
Set<Integer> cols = new HashSet<>(); // 已用的列
Set<Integer> diag1 = new HashSet<>(); // 主对角线 row-col 相同
Set<Integer> diag2 = new HashSet<>(); // 副对角线 row+col 相同
backtrackQueens(n, 0, queens, cols, diag1, diag2, result);
return result;
}
private static void backtrackQueens(int n, int row, int[] queens,
Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2,
List<List<String>> result) {
if (row == n) {
result.add(buildBoard(queens, n));
return;
}
for (int col = 0; col < n; col++) {
// 剪枝：检查当前位置是否合法
if (cols.contains(col)) continue; // 同列有皇后
if (diag1.contains(row - col)) continue; // 主对角线有皇后
if (diag2.contains(row + col)) continue; // 副对角线有皇后
// 做选择：在(row, col)放皇后
queens[row] = col;
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
// 递归：下一行
backtrackQueens(n, row + 1, queens, cols, diag1, diag2, result);
// 撤销选择
queens[row] = -1;
cols.remove(col);
diag1.remove(row - col);
diag2.remove(row + col);
}
}
private static List<String> buildBoard(int[] queens, int n) {
List<String> board = new ArrayList<>();
for (int row = 0; row < n; row++) {
char[] line = new char[n];
Arrays.fill(line, '.');
line[queens[row]] = 'Q';
board.add(new String(line));
}
return board;
}
public static void main(String[] args) {
System.out.println("全排列 [1,2,3]: " + permute(new int[]{1,2,3}));
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
System.out.println("含重复全排列 [1,1,2]: " + permuteUnique(new int[]{1,1,2}));
// [[1,1,2],[1,2,1],[2,1,1]]
System.out.println("子集 [1,2,3]: " + subsets(new int[]{1,2,3}));
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
System.out.println("组合总和 [2,3,6,7] target=7: " +
combinationSum(new int[]{2,3,6,7}, 7));
// [[2,2,3],[7]]
System.out.println("4皇后解数: " + solveNQueens(4).size()); // 2
System.out.println("8皇后解数: " + solveNQueens(8).size()); // 92
}
}四、踩坑实录
坑1：result.add(path)而不是result.add(new ArrayList<>(path))
这是最经典、最常见的回溯错误，新手几乎必踩。
报错现象：最终结果里所有的列表内容都是一样的（要么全是空，要么是最后一个状态）。
根本原因：path是一个引用，回溯过程中会被不断修改。如果直接result.add(path)，result里存的是同一个path对象的引用，等回溯结束时，所有result里的元素都指向同一个（已清空或已修改的）path。
具体解法：
// 错误：直接添加引用
result.add(path); // 所有结果都是同一个对象！
// 正确：添加副本
result.add(new ArrayList<>(path)); // 深拷贝当前状态坑2：去重时排序是前提，忘了排序
报错现象：含重复元素的全排列/组合，结果里有重复。
根本原因：去重逻辑nums[i] == nums[i-1]依赖相邻相同元素挨在一起，必须先排序。未排序的数组里，相同元素可能分散各处，条件无效。
具体解法：
// 去重套路必须配套排序
Arrays.sort(nums); // 排序是去重的前提，缺了这行去重条件无效坑3：N皇后判断冲突时用O(n)遍历而不是Set，超时
报错现象：N皇后实现逻辑正确，但N=12时超时（LeetCode时间限制）。
根本原因：每次放皇后时用O(row)循环检查所有已放置的皇后是否冲突，整体复杂度多了一个n倍。
具体解法：
// 错误：O(row)的冲突检查
private boolean isValid(int[] queens, int row, int col) {
for (int r = 0; r < row; r++) {
if (queens[r] == col) return false; // 同列
if (Math.abs(queens[r] - col) == Math.abs(r - row)) return false; // 同对角线
}
return true;
}
// 正确：用Set做O(1)判断（如上面的代码所示）
// 三个HashSet分别记录已用的列、主对角线(row-col)、副对角线(row+col)五、总结与延伸
回溯 = 做选择 + 递归 + 撤销选择，这是万用框架。 全排列、子集、N皇后的代码骨架完全相同，差异只在"选项从哪里来"和"结束条件是什么"。理解框架比背题目有价值得多。
去重的核心：排序让相同元素相邻，然后在for循环（树层）中跳过重复元素，在递归（树枝）中允许同一元素出现。 区分"树层去重"（
used[i-1]==false）和"树枝去重"（used[i-1]==true）是掌握含重复元素回溯题的关键。剪枝是回溯的性能关键。 组合总和里的
if (candidates[i] > remaining) break，N皇后里的三Set判断，都是剪枝。好的剪枝可以把实际时间复杂度从指数级降低到可接受范围，这是面试官评判回溯实现质量的重要维度。