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]说明遇到了重复的元素：
- used[i-1]==false 说明在同一层选择了重复的元素，重复的元素选择的位置会重复，之后产生的集合会重复，进行剪枝；
- used[i-1]==true 说明重复的元素在同一支，元素的位置没有出现重复，继续进行循环和回溯。
代码思路：
-
首先创建一个布尔数组
used，用于跟踪每个数字是否被使用过，对输入数组nums进行排序，以便后续去重操作。然后调用backTracking方法进行递归。 -
backTracking方法是核心递归函数，它通过深度优先搜索来生成所有可能的唯一排列组合。该方法接受两个参数：nums数组和一个表示哪些数字已经被使用的布尔数组used。 -
在
backTracking方法中，首先检查temp列表的大小是否达到了nums数组的长度。如果是，说明当前排列已经包含了所有的数字，将该排列添加到结果列表ans中，并返回。 -
如果
temp列表的大小没有达到nums数组的长度，则遍历nums数组的每个元素。如果当前元素已经被使用过（即used[i]为真），则跳过当前循环。 -
如果当前元素没有被使用过，需要进行额外的判断来避免重复生成相同的排列。具体来说，如果当前元素与前一个元素相同且前一个元素未被使用过，则跳过当前循环，以确保在当前位置上不会出现重复元素。
-
如果当前元素通过了重复判断，将其添加到
temp列表中，标记为已使用，并递归调用backTracking方法。递归返回后，需要将当前添加的元素从temp列表中移除，并标记为未使用，以便进行下一次循环时重新使用。 -
通过这种深度优先搜索的方式，不断尝试所有可能的唯一排列组合，直到所有数字都被使用过，生成了所有唯一排列组合。
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;
}
}
}
