首页 > 代码库 > [Leetcode] Permutations II

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

 

Solution:

 1 public class Solution { 2     public List<List<Integer>> permuteUnique(int[] num) { 3         Arrays.sort(num); 4         List<List<Integer>> result=new ArrayList<List<Integer>>(); 5         List<Integer> al=new ArrayList<Integer>(); 6         boolean[] flag=new boolean[num.length]; 7         dfs(num,result,al,0,flag); 8         return result; 9     }10 11     private void dfs(int[] num, List<List<Integer>> result, List<Integer> al, int level,boolean[] flag) {12         // TODO Auto-generated method stub13         if(level>num.length)14             return;15         if(level==num.length){16             result.add(new ArrayList<Integer>(al));17             return;18         }19         for(int i=0;i<num.length;++i){20             if(!flag[i]){21                 flag[i]=true;22                 al.add(num[i]);23                 dfs(num, result, al, level+1, flag);24                 al.remove(al.size()-1);25                 flag[i]=false;26                 while((i+1<num.length)&&num[i]==num[i+1])27                     ++i;28             }29         }    30     }31 }

 

[Leetcode] Permutations II