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

解题思路一：

发现自己想多了，代码直接拿来用，结果Time Limit Exceeded！看来还是不能直接用

解题思路二：

修改上述代码，去掉set，改用List，修改如下：

static public List
     
      
       > permuteUnique(int[] nums) {    	ArrayList
       
        
         > set=new ArrayList
         
          
           >(); dfs(set,nums,0); return set; } static List
           
             list=new ArrayList
            
             (); static public void dfs(List
             
              
               > set,int[] nums,int depth){ if(depth==nums.length){ set.add(new ArrayList
               
                (list)); return; } for(int i=0;i<=depth;i++){ while(i
               
              
             
            
           
          
         
        
       
      
     

 结果还是Time Limit Exceeded！看来不排序直接DFS这条路是走不通了。

解题思路三：

既然不排序直接DFS走不通，因此，可以考虑排序后，然后以字典的方式进行全排列添加，考虑到在题目中，我们已经写了一个字典的排列，稍作修改，添加boolean类型的返回值即可拿来用，JAVA实现如下：

static public List
     
      
       > permuteUnique(int[] nums) {    	ArrayList
       
        
         > set=new ArrayList
         
          
           >(); Arrays.sort(nums); do{ List
           
             list=new ArrayList
            
             (); for(int num:nums) list.add(num); set.add(list); }while(nextPermutation(nums)); return set; } static public boolean nextPermutation(int[] nums) { int index = nums.length - 1; while (index >= 1) { if (nums[index] > nums[index - 1]) { int swapNum=nums[index-1],swapIndex = index+1; while (swapIndex <= nums.length - 1&& swapNum < nums[swapIndex]) swapIndex++; nums[index-1]=nums[swapIndex-1]; nums[swapIndex-1]=swapNum; reverse(nums,index); return true; } index--; } reverse(nums,0); return false; } static void reverse(int[] nums,int swapIndex){ int[] swap=new int[nums.length-swapIndex]; for(int i=0;i
            
           
          
         
        
       
      
     

 结果Accepted！