题目描述（中等难度）

和上一道题类似，不同之处就是给定的数字中会有重复的，这样的话用之前的算法会产出重复的序列。例如，[ 1 1 ]，用之前的算法，产生的结果肯定是 [ [ 1 1 ]， [ 1 1 ] ]，也就是产生了重复的序列。但我们可以在上一题的解法中进行修改从而解决这道题。

解法一插入

这个没想到怎么在原基础上改，可以直接了当些，在它产生的结果里，对结果去重再返回。对于去重的话，一般的方法肯定就是写两个 for 循环，然后一个一个互相比较，然后找到重复的去掉。这里，我们用 39题解法二中提到的一种去重的方法。

解法二回溯

看下之前的算法


    List<List<Integer>> list = new ArrayList<>(); 
    backtrack(list, new ArrayList<>(), nums);
    return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
    if(tempList.size() == nums.length){
        list.add(new ArrayList<>(tempList));
    } else{
        for(int i = 0; i < nums.length; i++){ 
            if(tempList.contains(nums[i])) continue; // 已经存在的元素，跳过
            tempList.add(nums[i]); //将当前元素加入
            backtrack(list, tempList, nums); //向后继续添加
            tempList.remove(tempList.size() - 1); //将 tempList 刚添加的元素，去掉，尝试新的元素
        }
    }
}

假如给定的数组是 [ 1 1 3 ]，我们来看一下遍历的这个图。

第一个要解决的就是这句代码

换个思路，我们可以再用一个 list 保存当前 templist 中已经有的元素的下标，然后添加新元素的时候去判断下标就可以了。

第二个问题就是，可以看到有重复元素的时候，上边第 1 个图和第 2 个图产生的是完全一样的序列。所以第 2 个遍历是没有必要的。

解决的方案就是把数组首先排下顺序，然后判断一下上一个添加的元素和当前元素是不是相等，相等的话就跳过，继续下一个元素。

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    List<Integer> old = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums, old);
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, List<Integer> old) {
        list.add(new ArrayList<>(tempList));
    } else {
        for (int i = 0; i < nums.length; i++) { 
            //解决第一个问题
            if (old.contains(i)) {
                continue;
            }
            //解决第二个问题 !old.contains(i - 1) 很关键，下边解释下
            if (i > 0 && !old.contains(i - 1) && nums[i - 1] == nums[i]) {
                continue;
            }
            old.add(i);//添加下标
            tempList.add(nums[i]); // 将当前元素加入
            backtrack(list, tempList, nums, old); // 向后继续添加
            old.remove(old.size() - 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

解决第二个问题 !old.contains(i - 1) 很关键因为上边 old.contains(i) 代码会使得一些元素跳过没有加到 templist 上，所以我们要判断 nums[ i - 1 ] 是不是被跳过的那个元素，如果 old.contains ( i ) 返回 true ，即使 nums [ i - 1 ] == nums [ i ] 也不能跳过当前元素。因为上一个元素 nums [ i - 1 ] 并没有被添加到 templist。可能比较绕，但是可以参照上边的图，走一下流程就懂了。如果不加 !old.contains ( i - 1 )，那么图中的第 2 行的第 2 个 1 本来应该加到 tempList，但是会被跳过。因为第 2 行第 1 个元素也是 1。

对于解决第一个问题，我们用了一个 list 来保存下标来解决。需要一个 O ( n ) 的空间。有一种方法，我们可以用 O（1）的空间。不过前提是，我们需要对问题的样例了解，也就是给定的输入所包含的数字。我们需要找到一个样例中一定不包含的数字来解决我们的问题。

首先，我们假设输入的所有的数字中没有 -100 这个数字。

当然这个想法局限性很大，但是如果对解决的问题很熟悉，一般是可以找到这样一个不会输入的数字，然后可以优化空间复杂度。

解法三交换

这个改起来相对容易些，之前的想法就是在每一个位置，让每个数字轮流交换过去一下。这里的话，我们其实只要把当前位置已经有哪些数字来过保存起来，如果有重复的话，我们不让他交换，直接换下一个数字就可以了。

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> all = new ArrayList<>();
    Arrays.sort(nums);
    upset(nums, 0, all);
}
    if (begin == nums.length) {
        ArrayList<Integer> temp = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            temp.add(nums[i]);
        }
        all.add(new ArrayList<Integer>(temp));
        return;
    }
    HashSet<Integer> set = new HashSet<>(); //保存当前要交换的位置已经有过哪些数字了
    for (int i = begin; i < nums.length; i++) {
        if (set.contains(nums[i])) { //如果存在了就跳过，不去交换
            continue;
        }
        set.add(nums[i]);
        swap(nums, i, begin);
        upset(nums, begin + 1, all);
        swap(nums, i, begin);
    }
}
private void swap(int[] nums, int i, int begin) {
    int temp = nums[i];
    nums[i] = nums[begin];
}

总

基本上都是在上道题的基础上改出来了，一些技巧也是经常遇到，比如先排序，然后判断和前一个是否重复。利用 Hash 去重的功能。利用原来的存储空间隐藏掉数据，然后再想办法还原。

添加好友一起进步~

如果觉得有帮助的话，可以点击这里给一个 star 哦 ^^

47. Permutations II

题目描述（中等难度）

解法一 插入

解法二 回溯

解法三 交换

总

解法一插入

解法二回溯

解法三交换