LeetCode 46/51 排列型回溯题笔记-全排列 / N 皇后

目录

一、题目 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]是不同排列）。

核心思路

回溯法（选未用元素 + 标记回溯）：

1. 核心目标：选完所有元素，生成所有不重复的排列；
2. 去重逻辑：用boolean[] used标记已选元素，避免重复选；
3. 遍历规则：每一层递归都从i=0遍历所有元素，仅选used[i]=false的元素；
4. 终止条件：当前选择的组合长度 = 数组长度（所有元素都选完）；
5. 回溯操作：选元素时标记used[i]=true，递归返回后改回false，并移除当前元素。

重难点 & 易错点

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]为例）

二、题目 2：N 皇后（LeetCode 51）

题目描述

给定整数n，返回所有不同的n皇后问题的解决方案（皇后彼此不能攻击，即同一行、列、斜线无重复皇后）。

核心思路

回溯法（逐行放皇后 + 冲突约束）：

1. 核心目标：每行放一个皇后，满足 “列 / 正斜线 / 反斜线无冲突”；
2. 逐行策略：递归层对应 “当前行”，天然避免同一行冲突；
3. 冲突约束：
   • 列冲突：用Set<Integer> colUsed标记已用列；
   • 正斜线冲突：行-列为唯一标识，用diag1Used标记；
   • 反斜线冲突：行+列为唯一标识，用diag2Used标记；
4. 终止条件：当前行 = n（所有行都放好皇后）；
5. 回溯操作：放皇后时标记约束集合、修改棋盘，递归返回后撤销。

重难点 & 易错点

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为例，核心步骤）

三、排列型回溯题对比（全排列 vs N 皇后）

四、排列型 vs 子集 / 组合型回溯题对比

五、排列型回溯核心总结

1. 核心逻辑不变：依旧是「选分支→递归→回溯」的三板斧，差异仅在于 “选择分支的规则” 和 “约束条件的类型”；
2. 遍历规则：排列型必须从 0 遍历所有候选，靠 “标记 / 约束” 过滤无效分支；组合型从 start 遍历，靠 “范围” 过滤无效分支；
3. 约束转化：复杂排列题（如 N 皇后）的关键是把 “业务规则”（皇后不冲突）转化为 “可验证的数学条件”（斜线标识）；
4. 易错点通用：回溯时必须 “完全撤销选择”（包括集合 / 数组 / 棋盘的修改），结果集需 new 新对象避免引用污染。

六、如何快速区分并解决三类回溯题型

第一步：抓 3 个核心特征，快速归类

举例判断：

• 题目要求 “选 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移除候选元素; 恢复辅助变量; } }

分题型适配修改

第三步：避坑指南（按题型针对性避坑）

1. 子集 / 组合型避坑：
   • 不要用i=0遍历（会生成重复组合）；
   • 剪枝时计算maxI = n - need + 1，减少无效循环。
2. 基础排列型避坑：
   • 不要用start控制遍历（会丢失排列）；
   • 回溯时必须恢复used数组（否则后续选不到该元素）。
3. 进阶排列型避坑：
   • 先把 “业务规则” 转化为数学约束（如 N 皇后的斜线计算）；
   • 复杂路径（如棋盘）需逐位置修改 / 恢复，避免整体替换。

第四步：实战验证（以 3 道题为例）

核心原则

不管题型如何变化，回溯的本质是 “暴力枚举所有可能 + 剪枝”，只要抓住：

• 选什么（候选列表）；
• 怎么选（约束检查）；
• 何时停（终止条件）；
• 怎么回（撤销选择）；就能用同一套思路解决所有回溯题。

  ---