含重复元素的全排列如何去重？（全排列 II，LeetCode 47）

简化版

数组里有重复元素时，直接套全排列会产生重复的排列。去重两步走：先排序让相同元素相邻，再在每一层加一条剪枝——if (i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;。含义是：同一层里，如果前一个和我相等的元素还没被使用（说明它在这一层已经被试过又撤销了），我就跳过，避免同一层重复选相同的值。这叫「树层去重」。

详细版

List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);                         // ① 先排序，相同元素相邻
    backtrack(nums, new ArrayList<>(), new boolean[nums.length], res);
    return res;
}
void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = 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(nums, path, used, res);
        path.remove(path.size() - 1); used[i] = false;
    }
}

两个前提缺一不可：排序（让相同值相邻）+ 剪枝条件。
去重条件的核心是 !used[i-1]——表示相邻的相同值处于「同一层的兄弟位置」，跳过它防止同层重复。
复杂度最坏仍是 O(n × n!)，但重复越多、剪枝省得越多。

完整版教学

一、重复元素为什么产生重复排列

以 [1,1,2] 为例，如果当成三个不同元素 1a、1b、2，会排出 3!=6 个，但其中 [1a,1b,2] 和 [1b,1a,2] 其实长得一模一样（都是 [1,1,2]）。真正不同的排列只有 3 个：[1,1,2]、[1,2,1]、[2,1,1]。

根源：同一层里，用两个「值相同」的元素去填同一个位置，会长出完全一样的子树，导致重复解。去重就是要在同一层里，让相同的值只被选一次。

二、去重前提：先排序，让相同元素相邻

去重的第一步永远是 Arrays.sort(nums)。排序后所有相同的元素挨在一起（[1,1,2]），这样判断「我和前一个是不是相同值」只需比较 nums[i] 和 nums[i-1] 这对相邻元素，剪枝条件才能简洁地写出来。不排序，相同元素散落各处，没法用「和前一个比」的方式去重。

三、去重条件：!used[i-1] 的含义（同层剪枝）

核心剪枝：if (i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;

拆开看：

nums[i]==nums[i-1]：当前元素和前一个是相同的值（候选重复）；
!used[i-1]：前一个相同值没有被使用。

关键在理解 !used[i-1] 意味着什么。在回溯的一次 for 循环里，我们是在同一层横向遍历兄弟选择。如果前一个相同值 nums[i-1] 此刻 used 是 false，说明：它要么还没轮到（但同值我们本就要处理），要么它刚刚在本层被选过、递归回来又撤销了（撤销时置回了 false）。无论哪种，代表本层已经用这个值开过一棵子树了，此刻再用相同的 nums[i] 就是重复，跳过。

记忆点：!used[i-1] = 「前一个相同值和我是同一层的兄弟」→ 同层重复，剪掉。这叫树层去重（横向去重）。

四、为什么是 !used[i-1] 而不是 used[i-1]

两种写法其实都能去重，但含义和效率不同：

!used[i-1]（同层去重，推荐）：前一个相同值没被用 → 是同层兄弟 → 跳过。剪掉的是「同一层的重复」，是在决策树横向上去重，剪枝更靠前、更高效。
used[i-1]（同枝去重）：前一个相同值已被用（在当前路径的上一层）→ 允许当前用……这种写法要求「相同值必须按顺序、前一个先被用」，也能去重，但它是在纵向约束，产生的中间分支更多、效率略低。

两者结果都对，但 !used[i-1] 的「同层去重」更快，是面试标准答案。想清楚「横向（同层）」和「纵向（同枝）」的区别，是这题的深水区。

五、代码与剪枝效果

对 [1,1,2]（排序后仍是 [1,1,2]，下标 0、1 是两个 1）：

第一层选下标 0 的 1：正常展开；
第一层轮到下标 1 的 1：nums[1]==nums[0] 且 used[0]==false（下标 0 的 1 已在本层试过并撤销）→ 命中剪枝，跳过，不再开一棵重复子树；
第一层选下标 2 的 2：正常展开。

于是第一层只保留「以 1 开头」和「以 2 开头」两支，重复的「第二个 1 开头」被剪掉，最终得到 3 个不重复排列。

六、把状态、选择与撤销画成决策树

本题递归状态的精确定义是：排序后，同一树层只允许一组相等值中的第一个未使用元素作为代表；不同层仍可再次使用另一个副本。状态含义越清楚，结束条件、候选范围和去重位置越容易从题意推出。

进入节点：检查当前状态与剩余目标
枚举候选：先判断约束和剪枝条件
做选择：同步修改 path / used / 约束集合
递归下一层
撤销选择：恢复到进入本节点前的状态

带数字推演：[1a,1b,2] 根层若先选 1b 与先选 1a 会生成相同值序列，所以跳过前者；下一层可选另一个 1。画树时只需展开能体现“同层选择”和“纵向递归”区别的两三层，并标出被剪掉的分支，便能解释去重或剪枝为什么不会漏解。

记忆钩子：回溯不是“递归试一试”，而是维护状态不变量；做选择与撤销必须镜像，剪枝必须证明被删分支不可能产生答案。

七、复杂度、剪枝代价与实现边界

关键实现边界是：排序是相邻去重的前提；不能把 !used[i-1] 写反，否则会误删纵向合法选择。回溯复杂度不能只写一个固定模板，应说明树深、每层分支数、合法叶子数以及复制答案的成本。

维度	自检问题
状态	参数能否唯一描述当前节点
候选	是否遗漏合法选择或重复枚举
剪枝	条件是必要条件还是拍脑袋
撤销	path、标记和计数是否全部恢复
输出	保存的是快照还是共享可变引用

测试应包含无解、唯一解、多解、最小规模、全部候选相同或冲突密集的输入。对可变字符串、棋盘和标记数组，还应在递归返回后断言状态与进入前一致；这类断言比只比较最终答案更容易定位撤销错误。

八、常见误区与追问

误区：只用 HashSet 对最终结果去重就够。 会先生成大量重复叶子，浪费时间和内存。
误区：去重条件应是 used[i-1]。 标准同层剪枝用 !used[i-1]，表示前一个相同值没有在当前路径中占位。
误区：排序只是为了输出有序。 主要是让相等元素相邻，才能做局部剪枝。
追问：同层与同枝如何区分？ 同一 depth 的循环是同层，递归向下是同一枝。
追问：能否用每层 Set？ 可以，记录该层已尝试的值，代价是额外集合。
追问：复杂度怎样表达？ 与不同排列数量有关，最坏仍 O(n·n!)。

九、加强记忆

含重复元素的全排列去重：先排序（相同值相邻）+ 每层剪枝 if (nums[i]==nums[i-1] && !used[i-1]) continue;。!used[i-1] 表示「前一个相同值是同层兄弟、本层已用该值开过子树」，跳过实现树层（横向）去重。它比 used[i-1] 的同枝去重剪得更早、更高效。两个前提——排序 + 剪枝条件——缺一不可。

简化版

详细版