leetcode_47.全排列 II

47. 全排列 II

题目描述：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

判断去重的思路：

nums[i]==nums[i-1]说明遇到了重复的元素：

1. used[i-1]==false 说明在同一层选择了重复的元素，重复的元素选择的位置会重复，之后产生的集合会重复，进行剪枝；
2. used[i-1]==true 说明重复的元素在同一支，元素的位置没有出现重复，继续进行循环和回溯。

代码思路：

1. 首先创建一个布尔数组 used，用于跟踪每个数字是否被使用过，对输入数组 nums 进行排序，以便后续去重操作。然后调用 backTracking 方法进行递归。

2. backTracking 方法是核心递归函数，它通过深度优先搜索来生成所有可能的唯一排列组合。该方法接受两个参数：nums 数组和一个表示哪些数字已经被使用的布尔数组 used。

3. 在 backTracking 方法中，首先检查 temp 列表的大小是否达到了 nums 数组的长度。如果是，说明当前排列已经包含了所有的数字，将该排列添加到结果列表 ans 中，并返回。

4. 如果 temp 列表的大小没有达到 nums 数组的长度，则遍历 nums 数组的每个元素。如果当前元素已经被使用过（即 used[i] 为真），则跳过当前循环。

5. 如果当前元素没有被使用过，需要进行额外的判断来避免重复生成相同的排列。具体来说，如果当前元素与前一个元素相同且前一个元素未被使用过，则跳过当前循环，以确保在当前位置上不会出现重复元素。

6. 如果当前元素通过了重复判断，将其添加到 temp 列表中，标记为已使用，并递归调用 backTracking 方法。递归返回后，需要将当前添加的元素从 temp 列表中移除，并标记为未使用，以便进行下一次循环时重新使用。

7. 通过这种深度优先搜索的方式，不断尝试所有可能的唯一排列组合，直到所有数字都被使用过，生成了所有唯一排列组合。

class Solution {
    List<List<Integer>> ans = new LinkedList<>();
    List<Integer> temp = new LinkedList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums, used);
        return ans;
    }

    public void backTracking(int[] nums, boolean[] used) {
        if (temp.size() >= nums.length) {
            ans.add(new LinkedList<>(temp));
            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;

            temp.add(nums[i]);
            used[i] = true;
            backTracking(nums, used);
            temp.remove(temp.size() - 1);
            used[i] = false;
        }
    }
}