目录
一、题目 1：全排列（LeetCode 46）
题目描述
核心思路
重难点 & 易错点
Java 实现（标准版）
回溯过程演示（以nums=[1,2]为例）
二、题目 2：N 皇后（LeetCode 51）
题目描述
核心思路
重难点 & 易错点
Java 实现（标准版）
回溯过程演示（以n=4为例，核心步骤）
三、排列型回溯题对比（全排列 vs N 皇后）
四、排列型 vs 子集 / 组合型回溯题对比
五、排列型回溯核心总结
六、如何快速区分并解决三类回溯题型
第一步：抓 3 个核心特征，快速归类
第二步：套用对应解题模板（通用框架 + 适配修改）
通用回溯框架（所有题型都适用）
分题型适配修改
第三步：避坑指南（按题型针对性避坑）
第四步：实战验证（以 3 道题为例）
核心原则
排列型回溯的核心特征是：所有元素都要参与排列 / 放置，且需满足 “不重复 / 不冲突” 约束，和子集 / 组合型回溯的 “选部分元素” 有本质区别，以下是全排列、N 皇后两道核心题的完整总结。
一、题目 1：全排列（LeetCode 46）
题目描述
给定一个不含重复数字的数组nums，返回其所有可能的全排列（排列有顺序，如[1,2]和[2,1]是不同排列）。
核心思路
回溯法（选未用元素 + 标记回溯）：
- 核心目标：选完所有元素，生成所有不重复的排列；
- 去重逻辑：用
boolean[] used标记已选元素，避免重复选；- 遍历规则：每一层递归都从
i=0遍历所有元素，仅选used[i]=false的元素；- 终止条件：当前选择的组合长度 = 数组长度（所有元素都选完）；
- 回溯操作：选元素时标记
used[i]=true，递归返回后改回false，并移除当前元素。
重难点 & 易错点
| 类型 | 内容 |
|---|---|
| 重点 | 1. 用used数组替代组合题的start（排列需要选前面的元素，start会限制范围）；2. 递归层遍历所有元素（i=0开始）； |
| 难点 | 理解 “排列需要选所有元素” vs “组合选部分元素” 的核心差异； |
| 易错点 | 1. 误用组合题的start控制遍历起点（导致生成不完整排列）；2. 忘记回溯used数组（导致后续无法选该元素）；3. 直接添加current到结果集（引用污染，需new ArrayList<>(current)）； |
Java 实现（标准版）
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); List<Integer> current = new ArrayList<>(); boolean[] used = new boolean[nums.length]; // 默认全为false，无需手动初始化 backtrack(nums, used, current, result); return result; } private void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) { // 终止条件：选完所有元素 if (current.size() == nums.length) { result.add(new ArrayList<>(current)); // 必须new新列表，避免引用污染 return; } // 遍历所有元素，选未被使用的 for (int i = 0; i < nums.length; i++) { if (!used[i]) { // 选：标记已用，加入当前组合 used[i] = true; current.add(nums[i]); // 递归：处理下一层 backtrack(nums, used, current, result); // 回溯：撤销选择 current.removeLast(); used[i] = false; } } } }回溯过程演示（以nums=[1,2]为例）
| 递归层 | 遍历 i | used 状态 | current 状态 | 操作说明 |
|---|---|---|---|---|
| 初始层 | - | [F,F] | [] | 调用backtrack进入第一层 |
| 第一层 | 0 | [T,F] | [1] | 选 1，递归进入第二层 |
| 第二层 | 0 | [T,F] | [1] | used [0]=T，跳过 |
| 第二层 | 1 | [T,T] | [1,2] | 选 2，长度 = 2，加入结果[[1,2]] |
| 第二层 | - | [T,F] | [1] | 回溯，移除 2，used [1]=F |
| 第一层 | 0 | [F,F] | [] | 回溯，移除 1，used [0]=F |
| 第一层 | 1 | [F,T] | [2] | 选 2，递归进入第二层 |
| 第二层 | 0 | [T,T] | [2,1] | 选 1，长度 = 2，加入结果[[1,2],[2,1]] |
| 第二层 | - | [F,T] | [2] | 回溯，移除 1，used [0]=F |
| 第一层 | - | [F,F] | [] | 回溯，移除 2，used [1]=F |
二、题目 2：N 皇后（LeetCode 51）
题目描述
给定整数n，返回所有不同的n皇后问题的解决方案（皇后彼此不能攻击，即同一行、列、斜线无重复皇后）。
核心思路
回溯法（逐行放皇后 + 冲突约束）：
- 核心目标：每行放一个皇后，满足 “列 / 正斜线 / 反斜线无冲突”；
- 逐行策略：递归层对应 “当前行”，天然避免同一行冲突；
- 冲突约束：
- 列冲突：用
Set<Integer> colUsed标记已用列；- 正斜线冲突：
行-列为唯一标识，用diag1Used标记；- 反斜线冲突：
行+列为唯一标识，用diag2Used标记；- 终止条件：当前行 = n（所有行都放好皇后）；
- 回溯操作：放皇后时标记约束集合、修改棋盘，递归返回后撤销。
重难点 & 易错点
| 类型 | 内容 |
|---|---|
| 重点 | 1. 把 “皇后不冲突” 转化为三个约束集合的检查；2. 逐行递归，减少一层冲突判断；3. 棋盘的修改与回溯（StringBuilder 的setCharAt）； |
| 难点 | 1. 斜线冲突的数学表达（行 - 列、行 + 列）；2. 棋盘结果的格式转换（StringBuilder→String）； |
| 易错点 | 1. 斜线标识计算错误（如反斜线用行-列）；2. 忘记回溯约束集合（如colUsed.remove(col)）；3. 直接添加board到结果集（引用污染）； |
Java 实现（标准版）
class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<>(); // 初始化棋盘：每行都是n个'.' List<StringBuilder> board = new ArrayList<>(); for (int i = 0; i < n; i++) { StringBuilder row = new StringBuilder(); for (int j = 0; j < n; j++) { row.append('.'); } board.add(row); } // 约束集合：列、正斜线（行-列）、反斜线（行+列） Set<Integer> colUsed = new HashSet<>(); Set<Integer> diag1Used = new HashSet<>(); Set<Integer> diag2Used = new HashSet<>(); // 从第0行开始回溯 backtrack(n, 0, board, colUsed, diag1Used, diag2Used, result); return result; } private void backtrack(int n, int currentRow, List<StringBuilder> board, Set<Integer> colUsed, Set<Integer> diag1Used, Set<Integer> diag2Used, List<List<String>> result) { // 终止条件：所有行都放好皇后 if (currentRow == n) { // 转换棋盘格式（避免引用污染） List<String> solution = new ArrayList<>(); for (StringBuilder row : board) { solution.add(row.toString()); } result.add(solution); return; } // 遍历当前行的所有列，尝试放皇后 for (int col = 0; col < n; col++) { int diag1 = currentRow - col; // 正斜线唯一标识 int diag2 = currentRow + col; // 反斜线唯一标识 // 检查冲突：列/正斜线/反斜线都未被使用 if (!colUsed.contains(col) && !diag1Used.contains(diag1) && !diag2Used.contains(diag2)) { // 选：放皇后，标记约束 board.get(currentRow).setCharAt(col, 'Q'); colUsed.add(col); diag1Used.add(diag1); diag2Used.add(diag2); // 递归：处理下一行 backtrack(n, currentRow + 1, board, colUsed, diag1Used, diag2Used, result); // 回溯：撤销选择 board.get(currentRow).setCharAt(col, '.'); colUsed.remove(col); diag1Used.remove(diag1); diag2Used.remove(diag2); } } } }回溯过程演示（以n=4为例，核心步骤）
| 递归层（行） | 遍历列 | 约束检查结果 | 棋盘状态（简化） | 操作说明 |
|---|---|---|---|---|
| 0 | 0 | 冲突（后续验证） | [Q, ., ., .] | 选列 0，标记 col={0}、diag1={0}、diag2={0} |
| 1 | 0 | 列冲突 | - | 跳过 |
| 1 | 1 | 斜线冲突 | - | 跳过 |
| 1 | 2 | 斜线冲突 | - | 跳过 |
| 1 | 3 | 无冲突 | [Q, ., ., .][., ., ., Q] | 选列 3，标记 col={0,3}、diag1={0,-2}、diag2={0,4} |
| 2 | 0 | 列冲突 | - | 跳过 |
| 2 | 1 | 无冲突 | [Q, ., ., .][., ., ., Q][., Q, ., .] | 选列 1，标记 col={0,3,1}、diag1={0,-2,1}、diag2={0,4,3} |
| 3 | 0 | 列冲突 | - | 跳过 |
| 3 | 1 | 列冲突 | - | 跳过 |
| 3 | 2 | 无冲突 | [Q, ., ., .][., ., ., Q][., Q, ., .][., ., Q, .] | 选列 2，行 = 4，加入结果 |
三、排列型回溯题对比（全排列 vs N 皇后）
| 维度 | 全排列（LeetCode 46） | N 皇后（LeetCode 51） |
|---|---|---|
| 核心目标 | 生成所有元素的不重复排列 | 生成所有满足皇后不冲突的棋盘布局 |
| 选择分支 | 选 “未用的元素”（多分支，i=0 遍历） | 选 “当前行的列”（多分支，col=0 遍历） |
| 约束条件 | 元素不重复选（used 数组） | 列 / 正斜线 / 反斜线无冲突（三个 Set） |
| 递归层含义 | 选第 k 个元素 | 处理第 k 行的皇后放置 |
| 终止条件 | current.size () = 数组长度 | currentRow = n |
| 回溯对象 | List（current）+ 数组（used） | 棋盘（board）+ 三个 Set（约束） |
| 核心差异 | 无 “冲突” 概念，仅需标记已选元素 | 需将 “游戏规则” 转化为数学约束（斜线计算） |
四、排列型 vs 子集 / 组合型回溯题对比
| 维度 | 排列型（全排列 / N 皇后） | 子集 / 组合型（组合 / 组合总和 III） |
|---|---|---|
| 核心目标 | 所有元素参与排列 / 放置（全选） | 选部分元素组成子集 / 组合（选 k 个） |
| 遍历规则 | 每一层从 i=0 遍历所有候选（需标记已选） | 每一层从 start 遍历（天然避免重复选） |
| 去重 / 约束方式 | used 数组 / 冲突集合（允许选前面的元素） | start 控制起点（禁止选前面的元素） |
| 终止条件 | 选完所有元素（长度 / 行数达标） | 选够 k 个元素（或和达标） |
| 回溯核心 | 撤销 “已选标记 / 冲突标记” | 撤销 “元素选择” |
| 典型特征 | 结果有顺序（如 [1,2]≠[2,1]） | 结果无顺序（如 [1,2]=[2,1]） |
五、排列型回溯核心总结
- 核心逻辑不变：依旧是「选分支→递归→回溯」的三板斧，差异仅在于 “选择分支的规则” 和 “约束条件的类型”；
- 遍历规则：排列型必须从 0 遍历所有候选，靠 “标记 / 约束” 过滤无效分支；组合型从 start 遍历，靠 “范围” 过滤无效分支；
- 约束转化：复杂排列题（如 N 皇后）的关键是把 “业务规则”（皇后不冲突）转化为 “可验证的数学条件”（斜线标识）；
- 易错点通用：回溯时必须 “完全撤销选择”（包括集合 / 数组 / 棋盘的修改），结果集需 new 新对象避免引用污染。
六、如何快速区分并解决三类回溯题型
第一步：抓 3 个核心特征，快速归类
| 特征维度 | 子集 / 组合型 | 基础排列型（全排列） | 进阶排列型（N 皇后） |
|---|---|---|---|
| 1. 选元素数量 | 选 “部分”（k 个 / 任意个） | 选 “全部”（所有元素） | 选 “全部”（每行 1 个，共 n 个） |
| 2. 结果是否有序 | 无序（[1,2] 和 [2,1] 算一个） | 有序（[1,2] 和 [2,1] 算两个） | 无 “顺序” 概念，看布局合法性 |
| 3. 约束类型 | 数量 / 和约束（选 k 个 / 和为 n） | 仅 “不重复选” 约束 | 业务规则约束（皇后不冲突） |
举例判断：
- 题目要求 “选 3 个数和为 10”→ 子集 / 组合型；
- 题目要求 “生成数组所有排列”→ 基础排列型；
- 题目要求 “放置 n 个皇后不冲突”→ 进阶排列型。
第二步：套用对应解题模板（通用框架 + 适配修改）
通用回溯框架（所有题型都适用）
// 结果集 List<结果类型> result = new ArrayList<>(); // 当前路径 路径类型 current = 初始化; public 结果类型 solve(输入参数) { backtrack(输入参数, current, 辅助变量); return result; } private void backtrack(输入参数, 路径类型 current, 辅助变量) { // 1. 终止条件 if (终止条件满足) { result.add(新对象(current)); // 避免引用污染 return; } // 2. 遍历选择分支 for (候选元素 : 候选列表) { // 3. 约束检查：跳过无效分支 if (不满足约束) continue/break; // 4. 选：修改当前路径+辅助变量 加入候选元素到current; 更新辅助变量; // 5. 递归：处理下一层 backtrack(输入参数, current, 辅助变量); // 6. 回溯：撤销选择 从current移除候选元素; 恢复辅助变量; } }分题型适配修改
| 题型 | 终止条件修改 | 遍历候选列表修改 | 辅助变量 / 约束检查修改 |
|---|---|---|---|
| 子集 / 组合型 | current.size () == k / 和达标 | 从 start 开始遍历 | 无需 used，靠 start 去重 |
| 基础排列型 | current.size () == 数组长度 | 从 0 遍历所有元素 | 加 used 数组，检查！used [i] |
| 进阶排列型（N 皇后） | currentRow == n | 遍历当前行的所有列 | 加约束集合，检查列 / 斜线冲突 |
第三步：避坑指南（按题型针对性避坑）
- 子集 / 组合型避坑：
- 不要用
i=0遍历（会生成重复组合）；- 剪枝时计算
maxI = n - need + 1，减少无效循环。- 基础排列型避坑：
- 不要用
start控制遍历（会丢失排列）；- 回溯时必须恢复
used数组（否则后续选不到该元素）。- 进阶排列型避坑：
- 先把 “业务规则” 转化为数学约束（如 N 皇后的斜线计算）；
- 复杂路径（如棋盘）需逐位置修改 / 恢复，避免整体替换。
第四步：实战验证（以 3 道题为例）
| 题目 | 归类 | 核心适配点 |
|---|---|---|
| 组合（77） | 子集 / 组合型 | 终止条件current.size()==k，遍历i=start |
| 全排列（46） | 基础排列型 | 终止条件current.size()==nums.length，加 used 数组 |
| N 皇后（51） | 进阶排列型 | 终止条件currentRow==n，加列 / 斜线约束集合 |
核心原则
不管题型如何变化，回溯的本质是 “暴力枚举所有可能 + 剪枝”，只要抓住：
- 选什么（候选列表）；
- 怎么选（约束检查）；
- 何时停（终止条件）；
- 怎么回（撤销选择）；就能用同一套思路解决所有回溯题。
