这是一个系列介绍了回溯的回溯三问还有三种对应的模板题型分别是子集型组合型排列型。感兴趣去我主页查看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个位置该填谁问题回答当前操作从剩余可选的数字集合中枚举一个数填入排列的第i ii个位置子问题从剩余的数字中构造排列的第i 1 i1i1到第n − 1 n-1n−1位下一个子问题选了某个数字后从更少的剩余数字中继续构造后续排列2.2 搜索树可视化以nums [1, 2]为例每个节点枚举当前可以填的数字dfs(0)可选: {1, 2}选 1path [1]选 2path [2]dfs(1)可选: {2}dfs(1)可选: {1}dfs(2) → ✓ [1,2]dfs(2) → ✓ [2,1]⚠️核心要点每次选择一个数字后需要把它从可选集合中移除递归返回后再放回——这就是排列型回溯的**“恢复现场”**。2.3 代码实现更通用的做法是不维护一个集合而是使用布尔数组on_path来记录某个下标的数字是否已被选入路径。classSolution{privateListListIntegeransnewArrayList();privateListIntegerpathnewArrayList();privateint[]nums;privateboolean[]on_path;// 标记 nums[j] 是否已放入 pathpublicListListIntegerpermute(int[]nums){this.numsnums;on_pathnewboolean[nums.length];dfs(0);returnans;}privatevoiddfs(inti){// 边界所有位置都已填满得到一个完整排列if(inums.length){ans.add(newArrayList(path));// ⚠️ 必须拷贝path 是可变的return;}// 枚举所有数字尝试填入位置 ifor(intj0;jnums.length;j){if(!on_path[j]){// nums[j] 未被使用path.add(nums[j]);// 选择加入路径on_path[j]true;// 标记已占用dfs(i1);// 递归填下一个位置// 恢复现场回溯的核心on_path[j]false;// 取消标记path.remove(path.size()-1);// 移除末尾元素}}}}代码要点总结恢复现场递归返回后不仅要移除path末尾元素还要将on_path对应状态重置为false否则后续分支无法选择该数字。固定答案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_{m1}^{n} A(n,m) n! \times \left(\frac{1}{0!} \frac{1}{1!} \frac{1}{2!} \cdots \frac{1}{n!}\right)m1∑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 斜线冲突的判断与优化由于我们从上往下逐行放置判断斜线冲突只需看左上和右上两个方向对角线方向数学性质冲突条件右上方向主对角线行号 列号恒定r c R col[R]左上方向副对角线行号 - 列号恒定r - c R - col[R]基础版实现写一个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)判断冲突既然斜线冲突的本质是rc和r-c是否之前出现过我们完全可以把循环判断替换为布尔数组查表classSolution{privateListListStringansnewArrayList();privatechar[][]board;privateboolean[]col;// 列冲突privateboolean[]diag1;// 主对角线 (r c)privateboolean[]diag2;// 副对角线 (r - c n - 1)publicListListStringsolveNQueens(intn){boardnewchar[n][n];for(char[]row:board)Arrays.fill(row,.);colnewboolean[n];diag1newboolean[2*n];// r c 的范围: [0, 2n-2]diag2newboolean[2*n];// r - c n - 1 的范围: [0, 2n-2]dfs(0,n);returnans;}privatevoiddfs(intr,intn){if(rn){// 将棋盘转为字符串列表加入答案ListStringsolutionnewArrayList();for(char[]row:board)solution.add(newString(row));ans.add(solution);return;}for(intc0;cn;c){// 检查三个约束列、主对角线、副对角线if(col[c]||diag1[rc]||diag2[r-cn-1]){continue;// 冲突跳过}// 放置皇后board[r][c]Q;col[c]diag1[rc]diag2[r-cn-1]true;dfs(r1,n);// 递归下一行// 恢复现场board[r][c].;col[c]diag1[rc]diag2[r-cn-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!)。四、总结要点说明✅恢复现场递归返回后必须重置path与布尔状态on_path、col、diag✅固定答案记录答案时务必拷贝path或棋盘✅复杂度时间O ( n ⋅ n ! ) O(n \cdot n!)O(n⋅n!)空间O ( n ) O(n)O(n)除答案外✅N 皇后本质利用鸽巢原理将二维棋盘问题降维成一维排列问题✅优化技巧用布尔数组记录列和对角线占用状态实现O ( 1 ) O(1)O(1)冲突判断排列型回溯核心顺序不同即不同方案全排列问题N皇后问题当前操作从剩余可选数字中选一个填入位置 i状态维护布尔数组 on_path 记录已选元素复杂度分析利用 e 或放缩法证明为 O(n·n!)问题转化不能同行同列 → 本质是全排列斜线判断rc 与 r-c 的绝对值性质极致优化布尔数组记录对角线O(1) 判断冲突共同要点掌握排列型回溯的关键认知与子集/组合的区别排列关注顺序有n ! n!n!种方案通过on_path等机制维护剩余可选集合。N 皇后是带约束的排列利用鸽巢原理将二维棋盘问题降维成一维排列问题再通过布尔数组处理斜线约束。恢复现场与固定答案只要往path里动态添加元素递归返回后就必须移除记录答案时务必拷贝。掌握了全排列和 N 皇后你就拿下了回溯算法中最核心的一块版图。下期课程我们将正式开启动态规划的讲解感谢收看我们下期再见