import java.util.*;

public class Solution_Set {
    private Set<List<Integer>> resultSet = new HashSet<>();
    private boolean[] visited;
    
    public List<List<Integer>> permuteUnique(int[] nums) {
        visited = new boolean[nums.length];
        backtrack(nums, new ArrayList<>());
        return new ArrayList<>(resultSet);
    }
    
    private void backtrack(int[] nums, List<Integer> path) {
        if (path.size() == nums.length) {
            resultSet.add(new ArrayList<>(path)); // HashSet自动去重
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            path.add(nums[i]);
            visited[i] = true;
            backtrack(nums, path);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

缺陷分析

以 nums = [1,1,2] 为例，不去重会生成 3! = 6 个路径，但只有 3 个不重复排列。当 nums 含更多重复元素时，浪费更严重：

[1,1,1,2]：生成 4! = 24 条路径，只有 C(4,1) = 4 个不重复排列，浪费了 20 条。

复杂度分析

时间复杂度： O(n! × n)，生成所有（含重复）排列，并复制到 Set。
空间复杂度： O(n! × n)，HashSet 存储所有唯一排列。
额外开销： List 的 hashCode 计算和比较，常数因子大。

三、解法二：排序+剪枝（visited方式去重）

思路

关键条件： 先对 nums 排序，然后在回溯时加一个剪枝条件：

if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) continue;

条件解读：

i > 0：不是第一个元素，有前一个元素可以比较。
nums[i] == nums[i-1]：当前元素与前一个元素相同（因为排序后相同元素相邻）。
!visited[i-1]：前一个相同元素没有被当前路径使用。

为什么这个条件能去重？

这是很多人看不懂的地方，我来仔细解释。

排序后相同值的元素相邻，假设 nums = [1a, 1b, 2]（1a 和 1b 值相同，下标分别是0和1）。

当我们在某一层尝试选择时：

先选 1a（i=0），以 1a 为开头的所有排列都会被递归生成。
再选 1b（i=1），但 nums[1] == nums[0] 且 !visited[0]（此时我们在同一层选 1b，1a 没被当前路径使用），触发剪枝，跳过。

"1b 没被当前路径使用"表明：我们正处于"同一层"选1b的情况，此时以1b为开头的排列和以1a为开头的排列完全相同，因为1a和1b值相同。所以跳过。

反之，如果 visited[0] = true，说明 1a 已经在当前路径中（在更深层级被选了），此时 1b 可以正常选择，这不会产生重复（路径中1a和1b在不同位置）。

visited[i-1]=false: 同层选取重复值 → 剪枝（会生成重复排列）
visited[i-1]=true:  深层选取重复值 → 允许（不会生成重复排列）

代码

import java.util.*;

public class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private boolean[] visited;
    
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums); // 必须先排序，让相同元素相邻
        visited = new boolean[nums.length];
        backtrack(nums, new ArrayList<>());
        return result;
    }
    
    private void backtrack(int[] nums, List<Integer> path) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            
            // 去重剪枝：同层相同值只选第一个出现的
            if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) continue;
            
            path.add(nums[i]);
            visited[i] = true;
            backtrack(nums, path);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

Mermaid 图：去重剪枝的效果

复杂度分析

时间复杂度： O(n! × n) 最坏情况（无重复），但含重复时实际搜索树大幅缩减。
空间复杂度： O(n)，visited 数组 + 递归栈。

四、解法三：swap 方式去重

思路

swap 方式去重的思路与 visited 方式不同。在每一层，用一个 HashSet 记录"本层已经用过的值"，如果要选的值已经在本层用过，跳过。

注意：这里的 HashSet 是局部的（每层一个），不是全局的，每次进入新的递归层都创建一个新的 HashSet。

import java.util.*;

public class Solution_SwapDedup {
    private List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> permuteUnique(int[] nums) {
        backtrack(nums, 0);
        return result;
    }
    
    private void backtrack(int[] nums, int depth) {
        if (depth == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) perm.add(num);
            result.add(perm);
            return;
        }
        
        // 本层已使用的值（用于去重）
        Set<Integer> usedInThisLevel = new HashSet<>();
        
        for (int i = depth; i < nums.length; i++) {
            // 如果本层已经选过这个值，跳过
            if (usedInThisLevel.contains(nums[i])) continue;
            
            usedInThisLevel.add(nums[i]);
            
            swap(nums, depth, i);
            backtrack(nums, depth + 1);
            swap(nums, depth, i); // 回溯
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
    }
}

与解法二的比较

对比维度	排序+visited剪枝	swap+局部Set
是否需要排序	必须排序	不需要排序
去重机制	判断前一个相同元素是否被使用	局部Set记录本层使用过的值
代码复杂度	条件判断微妙，理解难度高	逻辑直观，容易理解
内存开销	O(n)	O(n)，每层一个Set
时间实际表现	更快（提前剪枝）	略慢（Set操作有开销）

复杂度分析

时间复杂度： O(n! × n) 最坏情况，含重复时大幅缩减。
空间复杂度： O(n)，递归栈 + 每层 Set（每层 Set 最多 n 元素）。

五、举一反三

去重剪枝的通用模式

去重问题的两种策略，可以推广到所有含重复元素的回溯题（子集II、组合总和II等）：

策略一：排序+条件剪枝

Arrays.sort(nums);
for (int i = start; i < nums.length; i++) {
    // 去重：同一层，跳过与前一个相同的值
    if (i > start && nums[i] == nums[i-1]) continue;
    // 注意：这里用 i > start 而不是 i > 0 && !visited[i-1]
    // 子集/组合问题中，"同层"通过 i >= start 来定义
    ...
}

策略二：局部Set

Set<Integer> seen = new HashSet<>();
for (int i = start; i < nums.length; i++) {
    if (seen.contains(nums[i])) continue;
    seen.add(nums[i]);
    ...
}

六、踩坑实录

坑一：剪枝条件 !visited[i-1] 与 visited[i-1] 搞反

// 错误：去掉了"深层重复使用"的情况
if (i > 0 && nums[i] == nums[i-1] && visited[i-1]) continue;

// 正确：去掉"同层重复使用"的情况
if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) continue;

如果用 visited[i-1]（已访问）作为剪枝条件，等于把深层使用的情况剪掉，而保留了同层使用的情况，结果完全相反！这个条件非常容易写反，要记清楚：!visited[i-1] 表示"1a 没在当前路径里"，即"同层"，这种情况下同层再选1b会重复，应剪枝。

坑二：忘记对 nums 排序

解法二的前提是 Arrays.sort(nums)。如果不排序，相同值的元素不相邻，nums[i] == nums[i-1] 的检查就无意义了。

坑三：swap 方式中的回溯路径不确定性

swap 方式有一个微妙的问题：每次 swap 后，nums 数组的顺序发生变化，后续递归看到的是"乱序"的 nums。因此，swap 方式不能用"当前元素与前一个相同就剪枝"这个策略，因为数组不保证有序。这就是为什么 swap 方式需要用局部 Set 而不是排序+条件的原因。

坑四：局部 Set 的作用域

Set<Integer> usedInThisLevel 必须在每次 backtrack 调用时重新创建，不能复用。如果复用，不同层的使用记录会相互干扰。

七、总结

全排列 II 是去重回溯的经典范例，两种去重方式（排序+条件 vs 局部Set）各有适用场景：

如果用 visited 数组，配合排序+剪枝条件，可以在树的中间层提前剪枝，效率更高。
如果用 swap 方式，配合局部 Set，不需要排序，逻辑更直观，但有额外的 Set 开销。

理解了这两种方式，后续的子集II（LeetCode 90）、组合总和II（LeetCode 40）的去重方式也都是这两种策略的应用。

解法	去重方式	是否需要排序	推荐程度
事后Set去重	结果集去重	否	不推荐
排序+条件剪枝	搜索中剪枝	是	推荐（面试必考）
swap+局部Set	搜索中剪枝	否	可接受

补充深入讲解：含重复元素去重的数学本质

去重条件 i > start && nums[i] == nums[i-1] 为什么正确

这个条件是含重复元素回溯题的核心剪枝，很多人只知道背这个条件，却不理解为什么这样写。让我们从头分析。

数组排序之后，相同值的元素聚在一起。在决策树的同一层（同一个父节点的所有子节点），我们要选择下一个放入路径的元素。如果同一层中有多个相同的元素，把它们都选一遍会产生完全相同的子树，从而生成重复的排列。去重的目标就是：同一层中，相同值的元素只选第一个。

条件 nums[i] == nums[i-1] 判断"当前元素和前一个元素值相同"。但这还不够，因为前一个元素 nums[i-1] 可能是在上层选的（已经在路径中），而不是在当前层被跳过的。只有当 nums[i-1] 是"在当前层被跳过"时，才意味着"相同值已经在当前层选过了"。

visited[i-1] == false 表示 nums[i-1] 没有被使用（不在当前路径中）。既然 nums[i-1] 的值和 nums[i] 相同，且 nums[i-1] 没被使用，说明如果我们此时选择 nums[i]，就相当于在当前层选了一个"已经被跳过的相同值"——这正是重复的情况，需要跳过。

反之，visited[i-1] == true 表示 nums[i-1] 在当前路径中（在上层已经被选走了），这时候 nums[i] 和路径中的 nums[i-1] 虽然值相同，但它们处于不同的位置，形成的排列是不同的，不需要跳过。

所以完整的去重条件是：nums[i] == nums[i-1] && !visited[i-1]（当前值和前一个相同，且前一个没被使用，说明在当前层已经选过相同值了，跳过）。

visited 方式去重与排序去重的等价性

另一种去重方式是在每一层维护一个 HashSet，记录当前层已经选过的值，如果遇到相同值就跳过。这两种方式是等价的，但性能不同。

HashSet 方式每次进入新的一层都需要创建一个新的 HashSet，销毁时需要 GC 回收，在递归层数较深时开销较大。而排序后 visited 方式只用一个全局 visited 数组，额外空间是 O(n)，没有动态内存分配。

在竞赛和面试中，排序+visited 方式是标准推荐写法，代码更简洁，性能更好。但 HashSet 方式逻辑更直观，初学时先理解 HashSet 方式，再学排序+visited 方式的等价变换，学习效果更好。

swap 方式的去重策略

swap 方式同样可以处理重复元素，但去重逻辑稍有不同。在 depth 层，for 循环从 i=depth 到 i=n-1 依次将 nums[i] 换到 depth 位置。为了避免将相同值的元素重复放到 depth 位置，我们在当前层维护一个 HashSet seen，记录已经放到 depth 位置的值：

如果 nums[i] 在 seen 中，跳过；否则将 nums[i] 加入 seen，然后 swap 并递归。这样可以保证每层每个不同的值只被选一次。

swap+HashSet 方式的缺点是需要在每一层动态创建 HashSet，但在实践中，由于 n 不大，这个开销可以忽略。优点是不需要预先排序，对输入顺序没有要求。

同层剪枝的可视化理解

以 nums=[1,1,2] 为例，排序后 nums=[1,1,2]。在第0层，选择第一个元素：

第一次：i=0，nums[0]=1，选择。向下递归，产生 [1,,] 形式的排列。第二次：i=1，nums[1]=1，visited[0]=false（nums[0]在当前层被跳过而不是在路径中），去重条件触发，跳过。第三次：i=2，nums[2]=2，选择。向下递归，产生 [2,,] 形式的排列。

如果不跳过 i=1，则第一次从 nums[0]=1 出发生成的 [1,,] 形状的排列，和第二次从 nums[1]=1 出发生成的 [1,,] 形状完全一样，产生重复。

去重的本质是：在同一层，相同的选择产生相同的子树。我们只保留每种值在当前层的第一次出现，砍掉后续重复出现，从而避免枚举重复的子树。

含重复元素全排列的工程意义

含重复元素的全排列在工程中有一个重要应用：多重集合的全排列枚举。例如在测试框架设计中，假设有若干测试环境参数，每个参数有若干可能值（部分值相同），需要枚举所有参数的不同组合来进行测试——这就是多重集合排列问题。

正确的去重策略在这类场景中能显著减少重复计算量。如果不去重，相同的测试配置会被执行多次，浪费资源；如果去重不正确，可能漏掉某些有效配置。

从算法设计的角度来看，含重复元素的回溯去重也体现了一个普遍原则：在枚举所有可能性时，通过提前识别"等价类"（产生相同结果的分支集合），只枚举每个等价类的一个代表，从而避免重复枚举。这个原则在组合优化、搜索算法中普遍适用。

含重复元素排列的实用总结

含重复元素全排列（LeetCode 47）是回溯去重的标准题，其核心去重条件 visited[i-1] == false 是需要深刻理解而非死记硬背的知识点。

理解的关键是"同层去重"的概念：在决策树的同一层（同一个父节点的所有子节点），如果有两个相同值的元素都可以被选择，选哪一个会产生完全相同的子树，从而产生重复排列。去重条件的作用就是保证同一层相同值只被选一次（选择排序后靠前的那个）。

不同层可以选相同值：在第一层选了值为 1 的元素，在第二层还可以选另一个值为 1 的元素，这样得到的排列中有两个 1，是合法且不重复的。去重条件不会阻止跨层的相同值选择，这正是 visited[i-1] 必须是 false（表示在当前层被跳过，而不是在上层已选）才触发去重的原因。

掌握这道题的去重逻辑，就能举一反三地处理含重复元素的子集、组合等类似问题。所有这类问题的去重核心思想都是相同的：排序聚合相同元素，在同层中相同值只选第一次出现的那个。

去重逻辑的代码记忆技巧

含重复元素全排列的去重代码只比无重复版多了三行：一是 Arrays.sort(nums) 排序；二是 boolean[] visited 数组；三是 if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) continue; 去重条件。把这三处差异和它们的理由记住，就能在无重复全排列的代码基础上快速写出含重复元素版本。

关键是理解 !visited[i-1] 的含义：前一个相同值没有被使用，说明它在当前层已经被跳过了，现在不能再选相同值的当前元素，否则产生重复。