登录排列算法完全指南 - 从全排列到N皇后，一套模板搞定所有排列问题
上篇文章我们聊了回溯算法中的组合/子集问题，本文将聚焦于LeetCode上面的：46（全排列）、47（全排列II）、22（括号生成）、51（N皇后）、37（解数独），以及剑指offer - 38（去重排列），这几道非常经典的题目，带领大家彻底拿下排列算法。
排列 VS 组合
基本概念
很多人容易把 排列 和 组合 混为一谈，但实际上它们有本质上的区别。它们的核心用一句话概括：
- 组合（Combination）：选出来就行，顺序不重要 [1,2] 和 [2,1] 是同一个。
- 排列（Permutation）：顺序很重要，[1,2] 和 [2,1] 是两个不同的结果。
通用模板
组合/回溯的通用模板
在本文开始之前，我们先回忆一下组合/回溯的通用模板：
function backtrack(路径, 选择列表) {
if (满足结束条件) {
result.push([...路径]); // 存放结果
return;
}
for (选择 in 选择列表) {
// 1. 做选择（前序遍历）
路径.push(选择);
// 2. 进入下一层决策树（递归）
backtrack(新的路径, 新的选择列表);
// 3. 撤销选择（后序遍历）
路径.pop();
}
}
排列的通用模板
const used = new Array(nums.length).fill(false); // 关键1：used数组
const backtrack = (path) => {
if (满足结束条件) {
result.push([...path]);
return;
}
// 关键2：每次都从0开始遍历
for (let i = 0; i < nums.length; i++) {
// 关键3：跳过已使用的元素
if (used[i]) continue;
// 做选择
path.push(nums[i]);
used[i] = true;
// 递归
backtrack(path);
// 撤销选择
path.pop();
used[i] = false;
}
};
排列 vs 组合的模板对比
| 对比维度 | 组合模板 | 排列模板 |
|---|---|---|
| 参数 | backtrack(start, path) | backtrack(path) |
| 遍历起点 | for (let i = start; i < n; i++) | for (let i = 0; i < n; i++) |
| 去重方式 | 用 start 控制不回头 | 用 used 数组标记 |
| 空间结构 | 不需要额外数组 | 需要 used 数组 |
| 结果数量 | C(n, k) | P(n, k) = n! |
为什么排列要每次都从0开始？
- 因为 [1,2] 和 [2,1] 是两个不同的结果
- 第一个位置可以选任何元素，第二个位置也可以选任何元素（除了已选的）
为什么需要 used 数组？
防止同一个元素被重复选取（排列不允许重复使用同一个元素）
下面的所有题都是在这个模版的基础上增加剪枝条件！
排列问题的入门（LeetCode 46）
题目
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例：nums = [1,2,3] 输出： [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
思路解析
排列问题的核心: 只要顺序不同，那就是不同的结果。比如第一个位置可以选1、2、3中的任意一个；选完第一个后，第二个位置只能在剩下的数中选。
图解过程
flowchart TD
Start(("[]"))
Start -->|"选1"| A1["[1]"]
Start -->|"选2"| A2["[2]"]
Start -->|"选3"| A3["[3]"]
A1 -->|"选2"| B1["[1,2]"]
A1 -->|"选3"| B2["[1,3]"]
A2 -->|"选1"| C1["[2,1]"]
A2 -->|"选3"| C2["[2,3]"]
A3 -->|"选1"| D1["[3,1]"]
A3 -->|"选2"| D2["[3,2]"]
B1 -->|"选3"| E1["[1,2,3]"]
B2 -->|"选2"| E2["[1,3,2]"]
C1 -->|"选3"| E3["[2,1,3]"]
C2 -->|"选1"| E4["[2,3,1]"]
D1 -->|"选2"| E5["[3,1,2]"]
D2 -->|"选1"| E6["[3,2,1]"]
代码实现
var permute = function(nums) {
const result = [];
const used = new Array(nums.length).fill(false);
const backtrack = (path) => {
// 结束条件：找到一个完整排列
if (path.length === nums.length) {
result.push([...path]);
return;
}
// 每次都从0开始，尝试所有未使用的元素
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue; // 已使用的跳过
// 做选择
path.push(nums[i]);
used[i] = true;
// 递归
backtrack(path);
// 撤销选择
path.pop();
used[i] = false;
}
};
backtrack([]);
return result;
};
全排列 II（LeetCode 47）—— 有重复元素的全排列
题目
给定一个可能包含重复数字的序列，返回所有不重复的全排列。
示例：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]
注意：不能有重复的排列。
思路解析
这题和上诉 46 题解析思路基本一致，唯一一点需要注意：当数组有重复元素时，需要去重，例如：两个 1 互换位置，但它们值相同，需要去重：
- 排序：让相同的元素挨在一起。
- 剪枝：在排列模板的基础上，增加同层去重判断。
代码实现
var permuteUnique = function(nums) {
const result = [];
const used = new Array(nums.length).fill(false);
nums.sort((a, b) => a - b); // 排序是去重的前提
const backtrack = (path) => {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
// 基础剪枝：已使用过的跳过
if (used[i]) continue;
// 去重剪枝：同一层相同元素跳过
if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
path.push(nums[i]);
used[i] = true;
backtrack(path);
path.pop();
used[i] = false;
}
};
backtrack([]);
return result;
};
字符串的排列（剑指Offer 38）
题目
输入一个字符串，打印出该字符串中字符的所有排列。可以以任意顺序返回这个字符串数组，但不能有重复元素。
示例：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]
思路解析
这题和上述 LeetCode 47 题完全一样，只是输入从数组变成了字符串。
代码实现
var permutation = function(s) {
const result = [];
const arr = s.split('');
const used = new Array(arr.length).fill(false);
arr.sort(); // 排序去重
const backtrack = (path) => {
if (path.length === arr.length) {
result.push(path.join(''));
return;
}
for (let i = 0; i < arr.length; i++) {
if (used[i]) continue;
// 去重：同一层相同字符跳过
if (i > 0 && arr[i] === arr[i - 1] && !used[i - 1]) continue;
path.push(arr[i]);
used[i] = true;
backtrack(path);
path.pop();
used[i] = false;
}
};
backtrack([]);
return result;
};
括号生成（LeetCode 22）—— 特殊的排列问题
题目
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例：n = 3 输出： [ "((()))", "(()())", "(())()", "()(())", "()()()" ]
思路解析
这题虽然看起来并不是传统的排列问题，但它本质上也是一个排列问题：
- 选择列表：( 和 ) 两个字符。
- 约束条件：左括号数量不超过 n，右括号数量不超过左括号数量。
- 不需要 used 数组，因为括号可以重复使用。
排列模板的变体
const backtrack = (path, left, right) => {
// 结束条件
if (left === n && right === n) { // TODO }
// 选择1：选左括号
if (left < n) {
backtrack(path + '(', left + 1, right);
}
// 选择2：选右括号
if (right < left) {
backtrack(path + ')', left, right + 1);
}
};
代码实现
var generateParenthesis = function(n) {
const result = [];
const backtrack = (path, left, right) => {
// 结束条件：左右括号都用完了
if (left === n && right === n) {
result.push(path);
return;
}
// 剪枝1：左括号数量不能超过 n
if (left < n) {
backtrack(path + '(', left + 1, right);
}
// 剪枝2：右括号数量不能超过左括号数量
if (right < left) {
backtrack(path + ')', left, right + 1);
}
};
backtrack('', 0, 0);
return result;
};
N皇后（LeetCode 51）—— 二维棋盘上的排列问题
题目
n 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击（即任意两个皇后都不能处于同一行、同一列或同一斜线上）。给你一个整数 n，返回所有不同的 n 皇后问题的解决方案。
示例：n = 4 输出： [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."],
["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
思路解析
N皇后问题可以看作一个特殊的排列问题：
- 每行只能放一个皇后，所以我们可以用 row 来表示当前处理到第几行
- 每列也只能放一个皇后，所以我们需要记录哪些列已经被占用
- 还需要考虑两个斜线方向
排列模板的变体
const backtrack = (row) => {
if (row === n) {
// 找到一个有效解
}
for (let col = 0; col < n; col++) {
if (isValid(row, col)) {
board[row] = col; // 相当于做选择
backtrack(row + 1); // 递归下一行
board[row] = -1; // 撤销选择
}
}
};
代码实现
var solveNQueens = function(n) {
const result = [];
// board 是一维数组，索引表示行，值表示该行皇后所在的列
const board = new Array(n).fill(-1);
// 检查在 (row, col) 放置皇后是否合法
const isValid = (row, col) => {
for (let i = 0; i < row; i++) {
// 检查列冲突
if (board[i] === col) return false;
// 检查对角线冲突：行差 === 列差
if (Math.abs(row - i) === Math.abs(col - board[i])) return false;
}
return true;
};
// 将 board 转换成题目要求的字符串数组格式
const formatBoard = () => {
return board.map(col => {
const row = new Array(n).fill('.');
row[col] = 'Q';
return row.join('');
});
};
const backtrack = (row) => {
// 结束条件：所有行都放置了皇后
if (row === n) {
result.push(formatBoard());
return;
}
// 在当前行尝试每一列
for (let col = 0; col < n; col++) {
if (!isValid(row, col)) continue; // 剪枝
// 做选择：在 (row, col) 放置皇后
board[row] = col;
// 递归到下一行
backtrack(row + 1);
// 撤销选择
board[row] = -1;
}
};
backtrack(0);
return result;
};
N皇后 vs 全排列：
| 维度 | 全排列 | N皇后 |
|---|---|---|
| 选择列表 | 所有未使用的数字 | 所有列 |
| 递归参数 | path | row |
| 约束条件 | 不能重复选 | 列、对角线不冲突 |
| 结束条件 | path.length === n | row === n |
解数独（LeetCode 37）—— 排列问题的终极形态
题目
编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则：
- 数字 1-9 在每一行只能出现一次
- 数字 1-9 在每一列只能出现一次
- 数字 1-9 在每一个 3x3 宫格内只能出现一次
思路解析
解数独是排列问题的终极形态，它结合了：
- 行的排列约束：每行数字不能重复。
- 列的排列约束：每列数字不能重复。
- 宫的排列约束：每个 3x3 宫格内数字不能重复。
排列模板的变体
const backtrack = () => {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] === '.') {
for (let num = 1; num <= 9; num++) {
if (isValid(i, j, num)) {
board[i][j] = num;
if (backtrack()) return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
};
代码实现
var solveSudoku = function(board) {
const isValid = (row, col, num) => {
const numStr = num.toString();
// 检查行
for (let i = 0; i < 9; i++) {
if (board[row][i] === numStr) return false;
}
// 检查列
for (let i = 0; i < 9; i++) {
if (board[i][col] === numStr) return false;
}
// 检查 3x3 宫格
const boxRow = Math.floor(row / 3) * 3;
const boxCol = Math.floor(col / 3) * 3;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[boxRow + i][boxCol + j] === numStr) return false;
}
}
return true;
};
const backtrack = () => {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
// 找到空白格
if (board[i][j] === '.') {
// 尝试填入 1-9
for (let num = 1; num <= 9; num++) {
if (isValid(i, j, num)) {
// 做选择
board[i][j] = num.toString();
// 递归
if (backtrack()) return true;
// 撤销选择
board[i][j] = '.';
}
}
return false; // 1-9 都不行，说明之前的选择有问题
}
}
}
return true; // 所有格子都填满了
};
backtrack();
return board;
};
排列问题的核心套路
做完这几道题，我们会发现它们其实都是排列思想的变形。
各题模板对比
| 题目 | 递归参数 | 选择列表 | 剪枝条件 | 特殊点 |
|---|---|---|---|---|
| 46.全排列 | path | 所有未使用元素 | used[i] | 无重复，基础模板 |
| 47.全排列II | path | 所有未使用元素 | used[i] + 同层去重 | 需要排序 + 去重 |
| 剑指38.字符串排列 | path | 所有未使用字符 | used[i] + 同层去重 | 和47一样 |
| 22.括号生成 | path, left, right | 左括号/右括号 | left < n 和 right < left | 不固定长度，约束特殊 |
| 51.N皇后 | row | 所有列 | 列冲突 + 对角线冲突 | 每行一个皇后，用一维数组记录 |
| 37.解数独 | 无（全局遍历） | 1-9 | 行+列+宫格约束 | 最复杂的排列问题 |
解题要点
- 排列用 used：排列问题都要用 used 数组记录哪些元素已用。
- 去重先排序：有重复元素时，排序 + 同层去重。
- 约束是剪枝：不合法的情况提前 continue 或 return。
- 递归深度是条件：路径长度等于元素个数时，收获结果。
结语
希望这篇文章能帮大家彻底搞懂排列算法。下次遇到"所有排列"、"全排列"、"N皇后"这类问题，别忘了拿出这个万能模板试一试！
对于文章中错误的地方或有任何疑问，欢迎在评论区留言讨论！
