Question:

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], and [2,1,1].

Thinking:

It’s very similiar with the question permutation, we should use backtracing to go through all the possibilities. For example, we pick the first element of the array, and get the permutation of the rest of this array, and put the first element in every possible position. The only difference bewteen the permutation is that we don’t allow duplicate. We can use hashset to solve this problem.

By the way, I made a mistake this time which I used to make. It’s that in the loop of this:

for (List<Integer> list: backtracing(nums, index+1)){
    for (int i = 0; i <= list.size(); i++){
        List<Integer> tempres = new ArrayList<Integer>(list);
        tempres.add(i, nums[index]);
        tres.add(tempres);
    }
}

I shouldn’t use the temporary variable list to operate, because
1) the size of it will change;
2) we should use it several times instead of once.
Then that means we should build another temporary variable. In this case, it’s tempres.

Solution:

public List<List<Integer>> permuteUnique(int[] nums) {
    return backtracing(nums, 0);
}

private List<List<Integer>> backtracing(int[] nums, int index) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    HashSet<List<Integer>> tres = new HashSet<List<Integer>>();
    int len = nums.length;

    if (index >= len){
        return res;
    }

    if (index == len - 1){
        List<Integer> tempres = new ArrayList<Integer>();
        tempres.add(nums[index]);
        res.add(tempres);
        return res;
    }

    for (List<Integer> list: backtracing(nums, index+1)){
        for (int i = 0; i <= list.size(); i++){
            List<Integer> tempres = new ArrayList<Integer>(list);
            tempres.add(i, nums[index]);
            tres.add(tempres);
        }
    }

    res.addAll(tres);
    return res;
}

There is another solution is much faster than me. Because it use extra space to record which element is used and use sort to reduce the extra cost to make sure unique. What’s more, the process of adding first and removing after dfs is usually used by people. I suppose I should learn from it.

Code:

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(nums==null || nums.length==0) return res;
    boolean[] used = new boolean[nums.length];
    List<Integer> list = new ArrayList<Integer>();
    Arrays.sort(nums);
    dfs(nums, used, list, res);
    return res;
}

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