题目：
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);
return res;
}
public void permutation_helper(int[] num, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> item,boolean[] visited){
if(item.size()==num.length){
res.add(new ArrayList<Integer>(item));
return;
}
for(int i = 0; i<num.length;i++){
if(i>0 && num[i-1] == num[i] && !visited[i-1])
continue;
if(!visited[i]){
item.add(num[i]);
visited[i]=true;
permutation_helper(num,res,item,visited);
item.remove(item.size()-1);
visited[i]=false;
}
}
}
实验：
如果未加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);
return res;
}
public void permutationhelper(ArrayList<ArrayList<Integer>> res, int[] num, ArrayList<Integer> item, int start){
if(item.size() == num.length){
res.add(new ArrayList<Integer>(item));
return;
}
for(int i = start; i < num.length; i++){
if(i > 0 && num[i] == num[i-1])
continue;
item.add(num[i]);
permutationhelper(res, num, item, start+1);
item.remove(item.size()-1);
}
}
为了更清楚的知道整个程序是如何运行的，代码中把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);
return res;
}
public void permutationhelper(ArrayList<ArrayList<Integer>> res, int[] num, ArrayList<Integer> item, boolean[] visited, int start){
if(item.size() == num.length){
res.add(new ArrayList<Integer>(item));
return;
}
for(int i = start; i < num.length; i++){
if(i > 0 && num[i] == num[i-1] && !visited[i - 1])
continue;
if(!visited[i]){
item.add(num[i]);
visited[i] = true;
permutationhelper(res, num, item, visited, start);
visited[i] = false;
item.remove(item.size()-1);
}
}
}