Problem
1. 题目简述
给出一列有重复的数，找出其所有的全排列。例如：
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
2. 算法思路
back tracking回溯法的经典题目之一，LeetCode 46. Permutations的进阶版，问题在于我们怎么去应对这个重复数字的问题。
如果按照以往的思路，对于这种有重复数字的，我们首先需要对数组进行排序，然后才能更好地去对重复数字进行处理。
那么我们能否还像permutation
1的时候，交换然后再找全排列么？不行的，这种去重方式的核心思想在于后面不会再出现比当前更小的数字，这么说可能有点抽象，我们来看个例子。
我们给出一个排好序的数组[1, 1, 2, 2, 3]，按照如上思路的话：
1. 从第1个数开始，分别和1、2、3、4、5进行替换，然后寻找其后面的全排列；
2. 为了不重复，我们每次（除了首次的自我替换）寻找替换的数字的时候，都要找到和当前不一样的数字为止，例如第1个1，和第2个1就不会进行替换，以此类推；
3. 那么问题会出在哪里呢？当我们需要替换第1个1和末尾的3时，数组变为[3, 1, 2, 2, 1]，然后我们找出[1, 2, 2, 1]的全排列;
4. 按照我们的逻辑，1先和第1个2替换，然后跳过第2个2，然后判断到了第2个1，第2个1和它之前的数字2是不同的，因此我们再次替换，到这里我们就会发现出现了重复，明明1和1不应该再替换的，在这里却被再次替换，所以会多出很多重复。
因此我们去重的方式其实可以更简单一点，用hashset来判断是之前是否和同样的元素交换过就可以了，而且原始数组不需要排序也可以。
回溯法
注意这里去重的方式和subset 2以及combination sum
2的去重方式完全不同，具体原因在上面已经详细描述了，建议自己尝试写一下，这里把错误的代码放在文章末尾，大家有兴趣可以自己debug一下，看看哪里出了问题。
这里我们使用hashset来去重。
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList();
if (nums.length == 0) {
return res;
}
getPermutations(nums, 0, res);
return res;
}
private void getPermutations(int[] nums, int start, List<List<Integer>> res) {
if (start == nums.length) {
List<Integer> solution = new ArrayList();
for (int num : nums) {
solution.add(num);
}
res.add(solution);
return;
}
Set<Integer> set = new HashSet();
for (int i = start; i < nums.length; i++) {
// 如果set中成功添加了num，则说明当前数字尚未和该数字交换过
if (set.add(nums[i])) {
swap(nums, start, i);
getPermutations(nums, start + 1, res);
swap(nums, start, i);
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}错误版本的代码，警戒
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList();
if (nums.length == 0) {
return res;
}
getPermutations(nums, 0, res);
// debug专用，找重复
// Set<List<Integer>> set = new HashSet();
// List<List<Integer>> newRes = new ArrayList();
// for (List<Integer> solution : res) {
// if (!set.add(solution)) {
// newRes.add(solution);
// }
// }
return res;
}
private void getPermutations(int[] nums, int start, List<List<Integer>> res) {
if (start == nums.length) {
List<Integer> solution = new ArrayList();
for (int num : nums) {
solution.add(num);
}
res.add(solution);
return;
}
for (int i = start; i < nums.length; i++) {
//这里的去重不行，有很多重复的case,这种写法对于[1,1,2,2,3]没问题，但是对于[0,0,1,1,2,2,3]有问题，自己可以尝试一下。
if (i > start && (nums[i] == nums[i - 1] || nums[start] == nums[i])) {
continue;
}
swap(nums, start, i);
getPermutations(nums, start + 1, res);
swap(nums, start, i);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}