我们吃透了子集和组合for管横向递归管纵向start管去重pop管还原。但排列题一上来就给你一记闷棍LC.77 组合 LC.46 全排列 for i in range(start, n): for i in range(n): ← 没有start ... if used[i]: continue ← 改用used判重 backtrack(i 1) backtrack(深度1) ← 下一层还是从0开始为什么排列不能用startstart强制下标递增消灭了[1,2]与[2,1]的重复。但排列题里[1,2]和[2,1]就是要同时存在的两个不同答案start恰恰把题目的答案给“优化”没了。排列必须换一套去重逻辑每一位都可以从0开始选但需要记住“哪些元素已经被用过”用过的不许再用——这就是used数组的由来。而LC.47那行著名的去重代码if i 0 and nums[i] nums[i-1] and not used[i-1]: continue十个人背得下、九个人说不清为什么是not used[i-1]。今天用决策树把它彻底讲透。 题目速览30秒读懂题目1全排列LC.46给定不含重复数字的数组nums返回所有可能的全排列。示例[1,2,3]→[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]约束n ≤ 6。题目2全排列IILC.47给定可包含重复数字的序列nums返回所有不重复的全排列。示例[1,1,2]→[[1,1,2],[1,2,1],[2,1,1]]注意只有3个不是6个约束n ≤ 8。注意[1,1,2]的全排列本来是6个那3个去哪了它们是被“两个1交换位置”产生的重复解必须被消灭。 核心思路used取代start再加一层“树层去重”模板对照三兄弟的分水岭选择范围判重手段答案位置递归传参LC.78 子集[start, n)无需判重每个节点start i 1LC.77 组合[start, n)无需判重深度k的节点start i 1LC.46 全排列[0, n)used[i] True跳过深度n的节点不传startLC.47 全排列II[0, n)①used[i]②同层相同值深度n的节点同上核心记忆点有start就不需要used顺序已经保证了不重复没有start就必须有used得自己记住谁用过二者是互斥的两套去重哲学排列的骨架backtrack(): if len(path) n: 收集 path[:]; return for i in range(n): # 每一位都可以从 0 开始选 if used[i]: continue # ★ 树枝去重本条路径上已经用过了 used[i] True; path.append(nums[i]) backtrack() path.pop(); used[i] False # 撤销path 和 used 必须成对还原LC.47的两层去重必须分清层次含义拦截条件类比树枝去重同一条路径纵深上同一个元素不能重复用used[i] True一个人不能在同一份名单里签两次名树层去重同一层横向里相同值的元素只能被选中一次nums[i] nums[i-1] and not used[i-1]同一层里有三个候选人重名只让第一个上场树枝去重是排列题本来就有的used树层去重才是LC.47新增的。灵魂拷问为什么是used[i-1] False而不是True结论used[i-1] False的真正含义是「和我同值的那个兄弟在本层已经被试过、并且已经回溯释放了」——它是“上一层纵向递归结束后留下的痕迹”因此它标识的是同一层。拆开看两种取值情形 Aused[i-1] True → nums[i-1]此刻正躺在当前path里它是我的祖先不是我的兄弟 → 说明我是在同一条树枝上往深处走选的是另一个下标上的相同值 → 这是合法且必须的[1,1,2] 里的第二个1就是这么被选中的 → 结论不能跳过 ✅ 保留 情形 Bused[i-1] False → nums[i-1]此刻不在path里可它又和我同值 → 那它只能是「本层前面那一轮for循环里被选中过、递归完又pop掉的元素」 → 也就是说本层已经用同值的元素生成过一棵一模一样的子树了 → 结论再选我就是纯重复 → 跳过 ✂关键洞察used[i-1] False之所以能精确标识“同一层”是因为回溯会把used还原成False。在同一层的for循环里第j轮选了nums[j]→ 递归 → 回来后used[j] False于是第j1轮看到的used[j]就是False。一句话记忆True 我上面的父亲纵向合法False 我左边的兄弟横向要砍为什么必须先排序判重条件只写了nums[i] nums[i-1]——只和它左边紧邻的那个元素比。如果相同的值不挨在一起比如[1,2,1]这个判断就完全失效。排序O(nlogn)把所有相同值聚到一起让“同值兄弟”变得相邻可比。排序是树层去重的前提不是可选优化。更易懂的替代写法每层一个setlevel_usedset()foriinrange(n):ifused[i]ornums[i]inlevel_used:continuelevel_used.add(nums[i])...它和used[i-1] False完全等价都需要先排序好处是一看就懂。面试策略先写used[i-1]版本主流写法再补一句“等价的还有每层set的写法”——能证明你是真懂。一个反直觉的实测发现写成True其实也能AC网上流传“used[i-1]写成True就错了”。我做了603组随机对拍n从2到8值域1~4用例解数False版节点数True版节点数[1,1,2]3912[1,1,1,2]41432[1,1,2,2]61933[1,1,1,1,2,2,3]1053501,958603组随机对拍汇总全部正确 ✅405,1681,437,8463.55倍两个版本答案都正确但True版要多走3.55倍的节点。为什么False版砍的是“本层的重复兄弟”重复分支在刚要展开时就被剪掉剪得早、剪得干净。True版砍的是“同值元素已被占用时不能再选它的右邻居”——它等价于规定了另一种规范化但剪枝发生得晚白白展开了大量注定重复的分支。结论used[i-1] False不是“唯一正确的写法”而是唯一高效的写法。️ 图解算法手把手走一遍LC.46nums [1,2,3]的排列树[] 第0层1个节点 ┌─────────────┼─────────────┐ 选1 选2 选3 [1] [2] [3] 第1层3个 ┌────┴────┐ ┌────┴────┐ ┌────┴────┐ 选2 选3 选1 选3 选1 选2 [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] 第2层6个 │ │ │ │ │ │ 选3 选2 选3 选1 选2 选1 [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] 第3层6个 ✅节点总数 1 3 6 6 16。通用公式Σ P(n,k) ≈ e · n!实测n10时节点数9,864,101 ≈ 2.718 × 10!。LC.47nums [1,1,2]的去重树重点看 ✂先排序 →[1,1,2]下标0、1都是1下标2是2。[] used[F,F,F] ┌───────────────────┬───────────────────┐ i0选nums[0]1 i1选nums[1]1 i2选nums[2]2 ✂ nums[1]nums[0]且used[0]False → 本层已用1试过了跳过 [1] [2] used[T,F,F] used[F,F,T] ┌─────┴─────┐ ┌──────┴──────────┐ i0 skip i1选1 i0选1 i1选1 used[0]True used[T,F,T] ✂ used[0]False → 跳过 → ★ 合法纵向递进 i2 选2 ┐ path[1,1] │ → [1,1,2] ✅ └→ [1,2] → 下一层i1: used[0]True → ★ 合法 → [1,2,1] ✅ [2] → i0 选1 → [2,1] → 下一层i1: used[0]True → ★ 合法 → [2,1,1] ✅逐帧看used的变化关键时刻当前层inums[i]used[i-1]判定结果1第 0 层01—合法选 →[1]2第 0 层11used[0]False同层重复✂ 跳过3第 0 层22值不同合法选 →[2]4第 1 层path[1]11used[0]True纵向递进合法选 →[1,1]5第 2 层path[1,1]22—合法✅ 收[1,1,2]6第 1 层path[1]22值不同合法选 →[1,2]7第 2 层path[1,2]11used[0]True纵向递进合法✅ 收[1,2,1]8第 1 层path[2]11used[0]False同层重复✂ 跳过时刻4和时刻8对比就是整道题的钥匙同样是“选第二个1”在[1]的下面选used[0]True是合法的纵深在[]的下面选used[0]False就是重复的横扩。实测[1,1,2]去重后只有9个节点不去重16个触发2次剪枝产出3个解。 代码实现Python JavaPython版classSolution:# LC.46 全排列used 取代 start defpermute(self,nums:List[int])-List[List[int]]:res,path[],[]used[False]*len(nums)nlen(nums)defbacktrack():iflen(path)n:# 填满n位 叶子res.append(path[:])returnforiinrange(n):# 没有startifused[i]:# 树枝去重continueused[i]Truepath.append(nums[i])backtrack()path.pop()used[i]Falsebacktrack()returnres# LC.47全排列II再加一层树层去重 defpermuteUnique(self,nums:List[int])-List[List[int]]:nums.sort()# 必须排序res,path[],[]used[False]*len(nums)nlen(nums)defbacktrack():iflen(path)n:res.append(path[:])returnforiinrange(n):ifused[i]:# 树枝去重纵向continue# 树层去重横向同值兄弟在本层已被试过并释放ifi0andnums[i]nums[i-1]andnotused[i-1]:continueused[i]Truepath.append(nums[i])backtrack()path.pop()used[i]Falsebacktrack()returnresJava版classPermuteSolution{privateListListIntegerres;privateListIntegerpath;privateboolean[]used;privateint[]nums;publicListListIntegerpermute(int[]nums){this.numsnums;this.resnewArrayList();this.pathnewArrayList();this.usednewboolean[nums.length];backtrack();returnres;}privatevoidbacktrack(){if(path.size()nums.length){res.add(newArrayList(path));return;}for(inti0;inums.length;i){if(used[i])continue;used[i]true;path.add(nums[i]);backtrack();path.remove(path.size()-1);used[i]false;}}}classPermuteUniqueSolution{privateListListIntegerres;privateListIntegerpath;privateboolean[]used;privateint[]nums;publicListListIntegerpermuteUnique(int[]nums){Arrays.sort(nums);// 必须排序this.numsnums;this.resnewArrayList();this.pathnewArrayList();this.usednewboolean[nums.length];backtrack();returnres;}privatevoidbacktrack(){if(path.size()nums.length){res.add(newArrayList(path));return;}for(inti0;inums.length;i){if(used[i])continue;if(i0nums[i]nums[i-1]!used[i-1])continue;used[i]true;path.add(nums[i]);backtrack();path.remove(path.size()-1);used[i]false;}}}⚠️防坑提醒used标记的是下标而非值两个 1 才能分别被选。撤销时path.pop()和used[i] False必须成对。LC.47的i 0不能省否则nums[-1]越界Python里会取到最后一个元素隐蔽bug。排序会原地修改nums不想动原数组请先拷贝。⏱️ 复杂度分析面试必问题目时间空间不计输出LC.46 全排列O(n·n!)O(n)LC.47 全排列 IIO(n·n!) 上界有重复时远小于此O(n)复杂度速记排列题答案规模是n!比组合的C(n,k) 和子集的2ⁿ涨得快得多。看到排列题先问n多大比先写代码重要。实测阈值n ≤ 8 轻松40,320条0.05sn 10 要6.7sn ≥ 12别做任何枚举。 举一反三6道高频变体题题目变化思路要点LC.31 下一个排列不求全部只求字典序下一个不用回溯右找下降 → 右找更大 → 交换 → 翻转后缀O(n)原地LC.60 第k个排列只求第k个康托展开 阶乘数制O(n²)LC.1079 活字印刷求所有长度的排列排列 每个节点都是答案LC.267 回文排列 II生成所有回文排列先统计频次判可行再生成“半边”排列剑指Offer 38字符串的排列同LC.47转字符数组后同一套模板LC.90 子集II有重复元素的子集排序 同层去重与今天同手法 面试追问模拟提前准备惊艳全场Q1为什么去重前必须排序判重条件nums[i] nums[i-1]只和紧邻的左邻居比较。不排序时相同值可能散落各处判断就漏判了。排序把所有相同值聚成连续块让“同值兄弟”相邻可比。排序是树层去重的前提不是可选优化。Q2used[i-1] False为什么能表示“同层”回溯会把used还原成False。在同一层的for循环里第j轮选了nums[j]→ 递归 → 回来后used[j] False于是第j1轮看到的used[j]就是False。所以“used为False的同值左邻居”精确等价于“本层已经尝试过的同值元素”。反过来used[i-1] True表示那个同值元素此刻正躺在path里是我的祖先选它下面的同值元素是纵向递进完全合法。False 我左边的兄弟要砍True 我上面的父亲要留。Q3字典序输出怎么做①先排序回溯按序选DFS访问顺序天然就是字典序② 用LC.31下一个排列反复求“下一个”空间O(1)。如果只求“第k个排列”LC.60用康托展开直接算每一位。Q4n!复杂度的题n多大就别想了实测阈值n ≤ 8轻松0.05sn 9~10勉强0.5s / 6.7sn ≥ 12别做枚举4.79亿条。必须换思路数学构造、康托展开或改问“有多少种”DP/组合计数。面试先问n的规模是新手和老手的区别。 实战小技巧刷题党必备口诀排列无startused记谁用树层看左邻False是兄弟True是父亲。模板排列 used 深度到n收集带重复 排序 !used[i-1]树层去重。防坑used标记下标撤销成对i 0不能省。 实际应用场景不止是刷题密码破解字典攻击空间枚举测试用例生成参数组合覆盖路径规划访问所有节点的顺序枚举游戏 AI走法排列搜索生物信息基因序列排列分析 今日思考题如果把去重条件改成used[i-1] True输出会变错吗提示见3.7节实测——答案仍然全对但节点数暴涨3.55倍。动手跑一遍[1,1,1,2]看看两个版本的节点数是不是14和32。