47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

本题开始并没有什么办法来解决重复数字的问题，后来想到了以前做过的contains duplicate的方法，可以先把数组排序，然后比较前一个数字和当前数字是否相等来判断是否有重复数字，但是
仍然解决不了本题，因为我们之前在permutation1里面用的排除法是list.contains()函数做的，如果用在这个题目上面，那么就不能把重复数字加入list里面了，我们就要另外设置一个used
数组来专门存放是否使用过该数字，数组的想法很巧妙，contains是对整体是否包含的排除，而used数组是对每一个number进行排除。判断当前used为false时候，看他前面的数字是否和他一样，
如果一样，并且used为false，则表示以前使用过这个，就不能再插入这个了，如果为true，则表示可以继续插入，因为是第一次插入。代码如下：

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtracking(nums,res,new ArrayList<Integer>(),new boolean[nums.length]);
        return res;
    }
    public void backtracking(int[] nums,List<List<Integer>> res,List<Integer> list,boolean[] used){
        if(list.size()==nums.length) res.add(new ArrayList<Integer>(list));
        else{
            for(int i=0;i<nums.length;i++){
                if(used[i]||i>0&&nums[i-1]==nums[i]&&used[i-1]) continue;
                used[i] = true;
                list.add(nums[i]);
                backtracking(nums,res,list,used);
                used[i] = false;
                list.remove(list.size()-1);
            }
        }
    }
}