企业官网建设流程全解析

这是一个系列介绍了回溯的"回溯三问"，还有三种对应的模板题型分别是子集型，组合型，排列型。感兴趣去我主页查看Leetcode专栏

一、什么是排列型回溯？

在子集型回溯中，元素是"选或不选"，且集合{ 1 , 2 } \{1,2\}{1,2}和{ 2 , 1 } \{2,1\}{2,1}视为相同。而在排列型回溯中，元素的顺序是重要的——{ 1 , 2 } \{1,2\}{1,2}和{ 2 , 1 } \{2,1\}{2,1}是两个不同的排列。

💡 直觉理解：n nn个互不相同的元素，第 1 个位置有n nn种选择，第 2 个位置有n − 1 n-1n−1种选择，……，第n nn个位置有1 11种选择。总排列数为n ! n!n!。

LeetCode 46 - 全排列：给定一个不含重复数字的数组nums，返回其所有可能的全排列。

# 输入: nums = [1, 2, 3]# 输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

与子集型回溯类似，我们依然可以用"回溯三问"来拆解问题。

二、全排列问题

2.1 回溯三问

站在输入的角度思考：我们要填排列的第i ii个位置，该填谁？

2.2 搜索树可视化

以nums = [1, 2]为例，每个节点枚举当前可以填的数字：

⚠️核心要点：每次选择一个数字后，需要把它从"可选集合"中移除，递归返回后再放回——这就是排列型回溯的**“恢复现场”**。

2.3 代码实现

更通用的做法是不维护一个集合，而是使用布尔数组on_path来记录某个下标的数字是否已被选入路径。

classSolution{privateList<List<Integer>>ans=newArrayList<>();privateList<Integer>path=newArrayList<>();privateint[]nums;privateboolean[]on_path;// 标记 nums[j] 是否已放入 pathpublicList<List<Integer>>permute(int[]nums){this.nums=nums;on_path=newboolean[nums.length];dfs(0);returnans;}privatevoiddfs(inti){// 边界：所有位置都已填满，得到一个完整排列if(i==nums.length){ans.add(newArrayList<>(path));// ⚠️ 必须拷贝！path 是可变的return;}// 枚举所有数字，尝试填入位置 ifor(intj=0;j<nums.length;j++){if(!on_path[j]){// nums[j] 未被使用path.add(nums[j]);// 选择：加入路径on_path[j]=true;// 标记：已占用dfs(i+1);// 递归：填下一个位置// 恢复现场（回溯的核心）on_path[j]=false;// 取消标记path.remove(path.size()-1);// 移除末尾元素}}}}

代码要点总结：

1. 恢复现场：递归返回后，不仅要移除path末尾元素，还要将on_path对应状态重置为false，否则后续分支无法选择该数字。
2. 固定答案：path是全局可变的，记录答案时必须做一次拷贝，否则所有答案都指向同一个对象。

2.4 复杂度分析：如何精确估算？

粗略估算：叶子节点有n ! n!n!个，路径长度为O ( n ) O(n)O(n)，所以时间复杂度是O ( n ⋅ n ! ) O(n \cdot n!)O(n⋅n!)。但如果我们想精确分析搜索树的节点总数，有两个进阶技巧：

方法一：高等数学做法（利用自然常数e ee）

从下往上计算节点总数，实际上是求和：

∑ m = 1 n A ( n , m ) = n ! × ( 1 0 ! + 1 1 ! + 1 2 ! + ⋯ + 1 n ! ) \sum_{m=1}^{n} A(n,m) = n! \times \left(\frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{n!}\right)m=1∑n​A(n,m)=n!×(0!1​+1!1​+2!1​+⋯+n!1​)

由高数知识可知，括号内的无穷级数正是自然常数e ee的定义。多出的部分乘上n ! n!n!后小于 1，因此节点总数可以精确表示为⌊ e ⋅ n ! ⌋ \lfloor e \cdot n! \rfloor⌊e⋅n!⌋。

方法二：初等数学做法（放缩法）

在O OO记号下只需估算上界：

• 最后一层有n ! n!n!个节点
• 往上每一层节点数至少减半（等比数列性质）
• 因此上面所有层的节点总数< 2 ⋅ n ! < 2 \cdot n!<2⋅n!
• 加上最后一层，总节点数< 3 ⋅ n ! < 3 \cdot n!<3⋅n!

结论：时间复杂度依然是O ( n ! ) O(n!)O(n!)。

结合拷贝路径的时间，最终时间复杂度为O ( n ⋅ n ! ) O(n \cdot n!)O(n⋅n!)，空间复杂度（除答案外）为O ( n ) O(n)O(n)。

三、N 皇后问题

LeetCode 51 - N 皇后：在n × n n \times nn×n的棋盘上放置n nn个皇后，使得它们不能同行、不能同列、不能同斜线。

3.1 问题转化：排列的本质

💡关键洞察：不能同行、不能同列 → 每行、每列恰好有一个皇后。

证明（反证法 + 鸽巢原理）：如果有某行没放皇后，剩下n − 1 n-1n−1行要放n nn个皇后，必然有一行至少放两个，矛盾。

因此，我们可以用数组col记录第i ii行的皇后放在第几列。col数组就是一个0 00到n − 1 n-1n−1的全排列！

如果不考虑斜线约束，N 皇后的搜索树和全排列完全一致。

3.2 斜线冲突的判断与优化

由于我们从上往下逐行放置，判断斜线冲突只需看左上和右上两个方向：

基础版实现：

写一个valid(r, c)函数，遍历之前的所有行，检查是否存在对角线冲突。每次判断需要O ( n ) O(n)O(n)，总时间复杂度为O ( n 2 ⋅ n ! ) O(n^2 \cdot n!)O(n2⋅n!)。

进阶版优化：O ( 1 ) O(1)O(1)判断冲突

既然斜线冲突的本质是r+c和r-c是否之前出现过，我们完全可以把循环判断替换为布尔数组查表！

classSolution{privateList<List<String>>ans=newArrayList<>();privatechar[][]board;privateboolean[]col;// 列冲突privateboolean[]diag1;// 主对角线 (r + c)privateboolean[]diag2;// 副对角线 (r - c + n - 1)publicList<List<String>>solveNQueens(intn){board=newchar[n][n];for(char[]row:board)Arrays.fill(row,'.');col=newboolean[n];diag1=newboolean[2*n];// r + c 的范围: [0, 2n-2]diag2=newboolean[2*n];// r - c + n - 1 的范围: [0, 2n-2]dfs(0,n);returnans;}privatevoiddfs(intr,intn){if(r==n){// 将棋盘转为字符串列表，加入答案List<String>solution=newArrayList<>();for(char[]row:board)solution.add(newString(row));ans.add(solution);return;}for(intc=0;c<n;c++){// 检查三个约束：列、主对角线、副对角线if(col[c]||diag1[r+c]||diag2[r-c+n-1]){continue;// 冲突，跳过}// 放置皇后board[r][c]='Q';col[c]=diag1[r+c]=diag2[r-c+n-1]=true;dfs(r+1,n);// 递归下一行// 恢复现场board[r][c]='.';col[c]=diag1[r+c]=diag2[r-c+n-1]=false;}}}

通过这种空间换时间的优化，我们将冲突判断从O ( n ) O(n)O(n)降到了O ( 1 ) O(1)O(1)。

📊 如果不考虑构造答案字符串的耗时，N 皇后的回溯时间复杂度被优化至O ( n ⋅ n ! ) O(n \cdot n!)O(n⋅n!)。

四、总结

掌握排列型回溯的关键认知：

1. 与子集/组合的区别：排列关注顺序，有n ! n!n!种方案；通过on_path等机制维护"剩余可选集合"。
2. N 皇后是带约束的排列：利用鸽巢原理将二维棋盘问题降维成一维排列问题，再通过布尔数组处理斜线约束。
3. 恢复现场与固定答案：只要往path里动态添加元素，递归返回后就必须移除；记录答案时务必拷贝。

掌握了全排列和 N 皇后，你就拿下了回溯算法中最核心的一块版图。下期课程我们将正式开启动态规划的讲解，感谢收看，我们下期再见！