47. Permutations II Leetcode Java

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].

Solution:

Advanced version of 46. Permutations

It allowed duplicates in the array which increase the difficulties of problem.

We can still use a boolean array to track used element, but we have to skip the duplicated element. Actually the solution I gave in 46 is the general solution, which is also the solution of this problem.

If an element is the first element in this iteration, we will use it, but we won't use any duplicated element after first one.

eg.[1,1,2] , 

 Some elements are skipped because of used array,

Some are skipped because of duplication. I marked the skipped elements caused by the duplication in the following recursion tree.

 

 public List<List<Integer>> permuteUnique(int[] num) {  
    List<List<Integer>> res=new ArrayList<List<Integer>>();  
    if(num==null || num.length==0) return res;  
    Arrays.sort(num);  
    boolean[] used=new boolean[num.length];  
    List<Integer> items= new ArrayList<Integer>();  
    helper(res,items,num,used);  
    return res;  
   }  
   public void helper(List<List<Integer>> res, List<Integer> items, int[] num, boolean[] used){  
     if(items.size()==num.length){  
       List<Integer> temp=new ArrayList<Integer>(items);  
       res.add(temp);  
       return;  
     }  
     for(int i=0;i<num.length;i++){  
       if(used[i]) continue;  
       used[i]=true;  
       items.add(num[i]);  
       helper(res,items,num,used);  
       used[i]=false;  
       items.remove(items.size()-1);  
       while(i+1<num.length && num[i+1]==num[i]) i++;  
     }   
   }