LeetCode LCR 084. 全排列 II
目录
题目描述
题意分析
给一个可包含重复数字的整数数组
nums，返回所有不重复的全排列。与上一题相比只改了一个前提——元素不再互不相同——但答案的判定标准随之变了：以前不同的下标选法必然给出不同的值序列，现在两个相同的值互换位置会产出一模一样的排列，必须只保留一份。
明确一下重复的来源。数组里若有 $k$ 个相同的值，它们之间的 $k!$ 种内部排布在值序列上是不可区分的。例如
[1,1,2]，把两个 1 当成可区分的个体会得到 $3! = 6$ 条路径，但去掉不可区分性后只有 3 个不同排列。所以本题的任务是：在搜索阶段就让每组相同值只按一种固定次序被取用，而不是搜完再拿哈希集合过滤。
数组长度上界只有 8，$8! = 40320$，即使不加任何去重也跑得完，但输出会带重复，判定不通过。这说明本题考的完全是正确性而非性能——出题人要看的是能否设计出无重无漏的枚举结构。元素取值
[-10, 10]含负数，排除掉一切以值为下标的标记技巧。
边界：全部元素相同（如
[2,2,2]）时答案只有 1 条，是检验去重是否彻底的最强用例；全部互不相同时应退化回 $n!$ 条，是检验有没有去重过头的用例。这两个极端都要能过。
解法：回溯搜索
核心思路
先沿用上一题的骨架：
used标记下标是否已用，第u层决定排列的第u位，横向枚举所有未用下标。这套结构会把[1,1,2]的两个 1 当成不同个体，产出 6 条路径，其中[1,1,2]出现两次、[1,2,1]出现两次、[2,1,1]出现两次。瓶颈很清楚：相同值之间的相对使用次序被枚举了 $k!$ 遍，而这些次序在答案里不可见。
关键观察是：既然相同值的内部次序不可见，那就人为规定一种唯一合法的次序——排序后让相同的值相邻，并强制它们必须从左往右依次被使用。也就是说，只有在
nums[i-1]已经进入当前路径之后，才允许使用nums[i]。这样 $k$ 个相同值的 $k!$ 种内部排布中，只有「按下标从小到大」那一种能走通，重复被压缩到恰好一份。
落成条件就是：当
i > 0 && nums[i] == nums[i-1] && !used[i-1]时跳过下标i。要维持的不变量是：path前u位已填好，used中恰有u个true，且对任意一组相同值，被标记为已用的那些下标构成该组的一个前缀。最后这一条正是去重的本体。
值得强调的是这个条件的否定形式：
used[i-1] == true时不跳过。这看起来反直觉——「前一个相同值已经用了，我还能用」——但恰恰是对的，因为这说明我们正沿着「从左往右依次取用」的合法次序前进，[1,1,2]里两个 1 都要被用到，正是靠这一条才没被误杀。反过来!used[i-1]意味着前一个相同值在本条路径的更早某层被用过又撤销了，也就是说以相同值开头的这棵子树刚刚已经完整搜过一遍，再搜就是重复。
解题步骤
- 先排序：
Arrays.sort(nums)。与组合去重同理，只有相同值相邻，nums[i] == nums[i-1]才能等价于「同一组相同值」。不排序的话[1,2,1]里两个 1 隔着一个 2，条件根本不触发。
- 准备
path与used：语义与上一题完全一致，used[i]表示下标i的元素是否已在当前路径中。
- 递归基：
u == n时深拷贝path存入结果并返回。
- 横向枚举所有下标并做两重过滤：
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;。第一重used[i]保证「每个位置只用一次」；第二重是去重，三个子条件缺一不可——i > 0防越界，nums[i] == nums[i-1]限定在同一组相同值内，!used[i-1]才是真正的判据。
- 选择、递归、撤销：
path.add与used[i] = true成对写在递归前，used[i] = false与path.remove成对写在递归后。Go 版把path预分配成定长切片并按位赋值path[u] = nums[i]，因此只需撤销used。
以
nums = [1, 1, 2]走一遍（已有序），下标记作 0、1、2。
dfs(u=0)，used = [F,F,F]。
i = 0：值 1，i > 0不成立，过滤不触发。path = [1]，used = [T,F,F]，进入dfs(1)。
dfs(1)层：i = 0已用跳过；i = 1值 1 与前一个相同，但used[0] == true，不跳过——这正是保留[1,1,...]的关键。path = [1,1]，used = [T,T,F]，进入dfs(2)；该层只有i = 2可用，得到第一个排列[1,1,2]。回溯撤销后，dfs(1)继续i = 2：path = [1,2]，used = [T,F,T]，进入dfs(2)；该层i = 1值 1 与前一个相同且used[0] == true，不跳过，得到第二个排列[1,2,1]。
回溯到
dfs(0)，撤销后used = [F,F,F]。i = 1：值 1 与nums[0]相同且used[0] == false，跳过。这次跳过挡掉的子树是「以第二个 1 开头」的全部路径，而它与刚刚搜完的「以第一个 1 开头」完全同构，正是重复来源。
i = 2：值 2，nums[2] != nums[1]，不跳过。path = [2]，used = [F,F,T]，进入dfs(1)；该层i = 0可用，path = [2,1]，used = [T,F,T]，进入dfs(2)，i = 1因used[0] == true不跳过，得到第三个排列[2,1,1]。回到dfs(1)的i = 1：此时used[0] == false，跳过，避免重复产出[2,1,1]。
最终答案恰为
[[1,1,2],[1,2,1],[2,1,1]]三条。若把条件里的!used[i-1]写成used[i-1]，则dfs(1)层的i = 1会被跳过，[1,1,2]和[1,2,1]都搜不到，输出只剩[2,1,1]。
代码实现
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int n = nums.length;
boolean[] used = new boolean[n];
// 排序让相同值相邻，是去重条件成立的前提。
Arrays.sort(nums);
dfs(0, n, nums, used, path, res);
return res;
}
// u：当前要填充的位置。
private void dfs(
int u, int n, int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
if (u == n) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < n; ++i) {
// used[i]：该下标已用；后半段：同组相同值必须从左往右依次取用。
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
path.add(nums[i]);
used[i] = true;
dfs(u + 1, n, nums, used, path, res);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
func permuteUnique(nums []int) [][]int {
n := len(nums)
res := make([][]int, 0)
// path 预分配定长，按位赋值，不需要显式撤销。
path := make([]int, n)
used := make([]bool, n)
// 排序让相同值相邻，是去重条件成立的前提。
sort.Ints(nums)
dfs(0, n, nums, used, path, &res)
return res
}
// u：当前要填充的位置。
func dfs(u, n int, nums []int, used []bool, path []int, res *[][]int) {
if u == n {
t := make([]int, n)
copy(t, path)
*res = append(*res, t)
return
}
for i := 0; i < n; i++ {
// used[i]：该下标已用；后半段：同组相同值必须从左往右依次取用。
if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue
}
path[u] = nums[i]
used[i] = true
dfs(u+1, n, nums, used, path, res)
used[i] = false
}
}
复杂度分析
- 时间复杂度：$O(n \times n!)$ 的上界，其中 $n$ 是数组长度。若数组中互不相同的值有各自的重数 $k_1, k_2, \dots$，实际产出的排列数是 $n! / (k_1! k_2! \cdots)$，去重条件把剩下的同构子树在进入前就砍掉，因此实际访问的节点数与答案规模同阶。每条答案拷贝耗时 $O(n)$，排序的 $O(n \log n)$ 可忽略。
- 空间复杂度：$O(n)$，递归栈深度恰为
n，path与used各占 $O(n)$。返回值按惯例不计入额外空间。
关键点总结
- 排列去重的判据是「同组相同值必须按下标从左往右依次使用」，实现成
nums[i] == nums[i-1] && !used[i-1]时跳过。这条规则给每个可区分的排列指定了唯一一条生成路径，是搜索去重的通用思路：为等价类挑一个代表元。!used[i-1]而不是used[i-1]是本题最大的坑，也是面试官必问的一点。答题时不要背口诀，要能说出「!used[i-1]意味着以相同值开头的同构子树刚被完整搜过」。- 组合去重与排列去重看似相似其实判据不同：组合里只需
i > u（同层跳过），排列里必须借助used[i-1]，因为排列的循环从0开始，「同层」这个概念不足以刻画重复。把这两者的差别讲清楚，比会写代码更能体现理解深度。- 排序是所有「相邻相同值」判据的前置条件，与题目是否要求有序无关。
- 用极端用例自查：全相同的输入应只产出 1 条，全不同的输入应产出 $n!$ 条。这两个数字能同时对上，去重逻辑基本就没问题了。
易错点总结
- 忘记排序：
nums = [1,2,1]时两个 1 不相邻，去重条件从不触发，输出 6 条含重复的排列。- 条件写成
used[i-1]而非!used[i-1]：nums = [1,1,2]会丢掉[1,1,2]和[1,2,1]，只输出[2,1,1]。- 漏掉
i > 0的边界判断：i = 0时访问nums[-1]，Java 抛数组越界异常，Go 直接 panic。- 漏掉
nums[i] == nums[i-1]，只判!used[i-1]：nums = [1,2,3]时几乎所有分支都被误杀，输出只剩[1,2,3]一条。- 忘记
used[i] = false：nums = [1,2]时首条排列产出后标记再不复位，后续分支全进不去，答案只剩 1 条。- Java 里只撤销
used而忘了path.remove：nums = [1,1,2]时path持续膨胀，第二条结果被记成长度大于 3 的数组。- 把
path引用直接放进res：nums = [1,1,2]最终输出 3 个内容相同的空列表。- Go 里写
*res = append(*res, path)不做copy：三条结果共享同一底层数组，全部变成最后一条[2,1,1]。- 改用
Set<List<Integer>>事后去重：nums = [1,1,1,1,1,1,1,1]时搜索树仍是 $8! = 40320$ 条路径，虽然勉强能过但白白多做了 40319 次无用功，面试中会被判定为没解决问题本身。- 在排序后用「跳过与前一个相同的值」这种组合式去重（即
i > 0 && nums[i] == nums[i-1]就跳过）：nums = [1,1,2]会连[1,1,2]都搜不出来，因为第二个 1 在任何层都被无条件屏蔽，输出只有[1,2,...]形态的残缺结果。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 47. 全排列 II | 中等 | 与本题完全同题，代码可原样提交 |
| 46. 全排列 | 中等 | 元素互不相同，无需排序与去重条件，是本题剥掉去重后的骨架 |
| LCR 083. 全排列 | 中等 | 与 46 同题，适合与本题并排对读，只差一行去重判断 |
| 面试题 08.08. 有重复字符串的排列组合 | 中等 | 把数组换成字符串，去重判据一字不改，可验证模板的迁移性 |
| 剑指 Offer 38. 字符串的排列 | 中等 | 字符串含重复字符，返回值是 String[]，需注意拼接时机 |
| 面试题 08.07. 无重复字符串的排列组合 | 中等 | 字符串版的 46，可对照体会「有无重复」在代码上的唯一差别 |
| 90. 子集 II | 中等 | 同样处理重复元素，但去重判据换成组合式的 i > u，可对比两种写法 |
| 60. 排列序列 | 困难 | 元素固定为 1~n 无重复，但只求第 k 个，需用阶乘逐位定位而非枚举 |
| LCR 082. 组合总和 II | 中等 | 重复元素的组合版去重，与本题构成「组合 vs 排列」的完整对照 |