企业官网建设流程全解析

我们吃透了子集和组合：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开始

为什么排列不能用start？
start强制下标递增，消灭了[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：全排列II（LC.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，再加一层“树层去重”

模板对照：三兄弟的分水岭

核心记忆点：

• 有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），树层去重才是LC.47新增的。

灵魂拷问：为什么是used[i-1] == False，而不是True？

结论：used[i-1] == False的真正含义是：「和我同值的那个兄弟，在本层已经被试过、并且已经回溯释放了」——它是“上一层纵向递归结束后留下的痕迹”，因此它标识的是同一层。

拆开看两种取值：

情形 A：used[i-1] == True → nums[i-1]此刻正躺在当前path里（它是我的"祖先"，不是我的"兄弟"） → 说明我是在同一条树枝上往深处走，选的是另一个下标上的相同值 → 这是合法且必须的！[1,1,2] 里的第二个1就是这么被选中的 → 结论：不能跳过 ✅ 保留 情形 B：used[i-1] == False → nums[i-1]此刻不在path里，可它又和我同值 → 那它只能是「本层前面那一轮for循环里被选中过、递归完又pop掉的元素」 → 也就是说：本层已经用同值的元素生成过一棵一模一样的子树了 → 结论：再选我就是纯重复 → 跳过 ✂

关键洞察：used[i-1] == False之所以能精确标识“同一层”，是因为回溯会把used还原成False。在同一层的for循环里，第j轮选了nums[j]→ 递归 → 回来后used[j] = False；于是第j+1轮看到的used[j]就是False。

一句话记忆：

• True= 我上面的父亲（纵向，合法）
• False= 我左边的兄弟（横向，要砍）

为什么必须先排序？

判重条件只写了nums[i] == nums[i-1]——只和它左边紧邻的那个元素比。如果相同的值不挨在一起（比如[1,2,1]），这个判断就完全失效。

排序（O(nlogn)）把所有相同值聚到一起，让“同值兄弟”变得相邻可比。排序是树层去重的前提，不是可选优化。

更易懂的替代写法：每层一个set

level_used=set()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）：

两个版本答案都正确，但True版要多走3.55倍的节点。为什么？

• False版砍的是“本层的重复兄弟”：重复分支在刚要展开时就被剪掉，剪得早、剪得干净。
• True版砍的是“同值元素已被占用时不能再选它的右邻居”——它等价于规定了另一种规范化，但剪枝发生得晚，白白展开了大量注定重复的分支。

结论：used[i-1] == False不是“唯一正确的写法”，而是唯一高效的写法。

🖼️ 图解算法（手把手走一遍）

LC.46：nums = [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!，实测n=10时节点数9,864,101 ≈ 2.718 × 10!。

LC.47：nums = [1,1,2]的去重树（重点看 ✂）

先排序 →[1,1,2]（下标0、1都是1，下标2是2）。

[] used=[F,F,F] ┌───────────────────┬───────────────────┐ i=0选nums[0]=1 i=1选nums[1]=1 i=2选nums[2]=2 ✂ nums[1]==nums[0]且used[0]==False → 本层已用1试过了，跳过！ [1] [2] used=[T,F,F] used=[F,F,T] ┌─────┴─────┐ ┌──────┴──────────┐ i=0 skip i=1选1 i=0选1 i=1选1 used[0]==True used=[T,F,T] ✂ used[0]==False → 跳过 → ★ 合法！纵向递进 i=2 选2 ┐ path=[1,1] │ → [1,1,2] ✅ └→ [1,2] → 下一层i=1: used[0]==True → ★ 合法 → [1,2,1] ✅ [2] → i=0 选1 → [2,1] → 下一层i=1: used[0]==True → ★ 合法 → [2,1,1] ✅

逐帧看used的变化（关键）：

时刻4和时刻8对比，就是整道题的钥匙：同样是“选第二个1”，在[1]的下面选（used[0]=True）是合法的纵深，在[]的下面选（used[0]=False）就是重复的横扩。

实测：[1,1,2]去重后只有9个节点（不去重16个），触发2次剪枝，产出3个解。

💻 代码实现（Python + Java）

Python版

classSolution:# ============ LC.46 全排列：used 取代 start ============defpermute(self,nums:List[int])->List[List[int]]:res,path=[],[]used=[False]*len(nums)n=len(nums)defbacktrack():iflen(path)==n:# 填满n位 = 叶子res.append(path[:])returnforiinrange(n):# 没有start！ifused[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)n=len(nums)defbacktrack():iflen(path)==n:res.append(path[:])returnforiinrange(n):ifused[i]:# 树枝去重（纵向）continue# 树层去重（横向）：同值兄弟在本层已被试过并释放ifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack()path.pop()used[i]=Falsebacktrack()returnres

Java版

classPermuteSolution{privateList<List<Integer>>res;privateList<Integer>path;privateboolean[]used;privateint[]nums;publicList<List<Integer>>permute(int[]nums){this.nums=nums;this.res=newArrayList<>();this.path=newArrayList<>();this.used=newboolean[nums.length];backtrack();returnres;}privatevoidbacktrack(){if(path.size()==nums.length){res.add(newArrayList<>(path));return;}for(inti=0;i<nums.length;i++){if(used[i])continue;used[i]=true;path.add(nums[i]);backtrack();path.remove(path.size()-1);used[i]=false;}}}classPermuteUniqueSolution{privateList<List<Integer>>res;privateList<Integer>path;privateboolean[]used;privateint[]nums;publicList<List<Integer>>permuteUnique(int[]nums){Arrays.sort(nums);// 必须排序this.nums=nums;this.res=newArrayList<>();this.path=newArrayList<>();this.used=newboolean[nums.length];backtrack();returnres;}privatevoidbacktrack(){if(path.size()==nums.length){res.add(newArrayList<>(path));return;}for(inti=0;i<nums.length;i++){if(used[i])continue;if(i>0&&nums[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，不想动原数组请先拷贝。

⏱️ 复杂度分析（面试必问）

复杂度速记：排列题答案规模是n!，比组合的C(n,k) 和子集的2ⁿ涨得快得多。看到排列题先问n多大，比先写代码重要。

实测阈值：n ≤ 8 轻松（40,320条，0.05s）；n = 10 要6.7s；n ≥ 12别做任何枚举。

🚀 举一反三：6道高频变体题

💬 面试追问模拟（提前准备，惊艳全场）

Q1：为什么去重前必须排序？

判重条件nums[i] == nums[i-1]只和紧邻的左邻居比较。不排序时相同值可能散落各处，判断就漏判了。排序把所有相同值聚成连续块，让“同值兄弟”相邻可比。排序是树层去重的前提，不是可选优化。

Q2：used[i-1] == False为什么能表示“同层”？

回溯会把used还原成False。
在同一层的for循环里，第j轮选了nums[j]→ 递归 → 回来后used[j] = False；
于是第j+1轮看到的used[j]就是False。所以“used为False的同值左邻居”精确等价于“本层已经尝试过的同值元素”。反过来used[i-1] == True表示那个同值元素此刻正躺在path里（是我的祖先），选它下面的同值元素是纵向递进，完全合法。False = 我左边的兄弟（要砍），True = 我上面的父亲（要留）。

Q3：字典序输出怎么做？

①先排序，回溯按序选，DFS访问顺序天然就是字典序；
② 用LC.31下一个排列反复求“下一个”，空间O(1)。如果只求“第k个排列”（LC.60），用康托展开直接算每一位。

Q4：n!复杂度的题，n多大就别想了？

实测阈值：n ≤ 8轻松（0.05s）；n = 9~10勉强（0.5s / 6.7s）；n ≥ 12别做枚举（4.79亿条）。必须换思路：数学构造、康托展开，或改问“有多少种”（DP/组合计数）。面试先问n的规模，是新手和老手的区别。

🧩 实战小技巧（刷题党必备）

• 口诀：排列无start，used记谁用；树层看左邻，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。