题目：
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].
题解：
这道题跟Permutaitons没啥大的区别，就是结果去重。
我之前也有写过去重的两个方法:
一个是在加入结果的时候用contains判断，一个是在找结果的时候看他是不是跟前一个元素相同。
这道题还要考虑的是visited情况，前一个元素就算跟当前元素相同，如果visited==true也没关系。但是如果前面元素跟当前元素相同还没被visited，那么就要做去重处理了。
代码如下：
1 public ArrayList<ArrayList<Integer>> permuteUnique( int[] num) { 2 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 3 ArrayList<Integer> item = new ArrayList<Integer>(); 4 5 if(num.length==0||num== null) 6 return res; 7 boolean[] visited = new boolean[num.length]; 8 Arrays.sort(num); 9 permutation_helper(num,res,item,visited); 10 return res; 11 } 12 13 public void permutation_helper( int[] num, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> item, boolean[] visited){ 14 if(item.size()==num.length){ 15 res.add( new ArrayList<Integer>(item)); 16 return; 17 } 18 19 for( int i = 0; i<num.length;i++){ 20 if(i>0 && num[i-1] == num[i] && !visited[i-1]) 21 continue; 22 if(!visited[i]){ 23 item.add(num[i]); 24 visited[i]= true; 25 permutation_helper(num,res,item,visited); 26 item.remove(item.size()-1); 27 visited[i]= false; 28 } 29 } 30 }
实验：
如果未加visited判断的话，将会出现下面的错误：
| Input: | [1,1] |
| Output: | [] |
| Expected: | [[1,1]] |
因为执行了去重处理，所以一个结果都没有保留
同时，这里在每次添加遍历的item时候，没有判断该元素是否之前被visited过，这样同样会产生重复。
另外一个错误是，for循环的起始是start，而非每次从0开始，这样的话，会忽略掉start位置之前，未visited过的，非重复值。
比如： [1, 2]，第一次记录结果[1,2]是正常的没有问题。 但是当退栈到第一个栈，走for循环时，item位置的第一个元素是2, 进入下一层递归，发现start位置是1（0+1），1位置上面是元素2，2被visited过了，所以就结束了这个程序。那么位置在0的，值为1的元素，就被忽略掉了。因为start位置没有从0开始，所以每次都应该从0位置开始。
错误代码如下：
1 public ArrayList<ArrayList<Integer>> permuteUnique( int[] num) { 2 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 3 ArrayList<Integer> item = new ArrayList<Integer>(); 4 5 if(num == null || num.length == 0) 6 return res; 7 // boolean [] visited = new boolean[num.length]; 8 Arrays.sort(num); 9 permutationhelper(res, num, item, 0); 10 return res; 11 } 12 13 public void permutationhelper(ArrayList<ArrayList<Integer>> res, int[] num, ArrayList<Integer> item, int start){ 14 if(item.size() == num.length){ 15 res.add( new ArrayList<Integer>(item)); 16 return; 17 } 18 19 for( int i = start; i < num.length; i++){ 20 if(i > 0 && num[i] == num[i-1]) 21 continue; 22 23 item.add(num[i]); 24 permutationhelper(res, num, item, start+1); 25 item.remove(item.size()-1); 26 } 27 }
为了更清楚的知道整个程序是如何运行的，代码中把start标记标出，正确代码如下：
1 public ArrayList<ArrayList<Integer>> permuteUnique( int[] num) { 2 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 3 ArrayList<Integer> item = new ArrayList<Integer>(); 4 5 if(num == null || num.length == 0) 6 return res; 7 boolean [] visited = new boolean[num.length]; 8 Arrays.sort(num); 9 permutationhelper(res, num, item, visited, 0); 10 return res; 11 } 12 13 public void permutationhelper(ArrayList<ArrayList<Integer>> res, int[] num, ArrayList<Integer> item, boolean[] visited, int start){ 14 if(item.size() == num.length){ 15 res.add( new ArrayList<Integer>(item)); 16 return; 17 } 18 19 for( int i = start; i < num.length; i++){ 20 if(i > 0 && num[i] == num[i-1] && !visited[i - 1]) 21 continue; 22 if(!visited[i]){ 23 item.add(num[i]); 24 visited[i] = true; 25 permutationhelper(res, num, item, visited, start); 26 visited[i] = false; 27 item.remove(item.size()-1); 28 } 29 } 30 }