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].
解题思路：
Permutations 那题输入是不包含重复元素的，故生成的排列都是不同的，II中输入元素可能相同
因而可能会产生相同的排列，这里需要去重，没有找到很好的剪枝条件，这里使用HashSet来去重，
当发现已经添加过该组合则不会再添加
public boolean add(E e)
如果此 set 中尚未包含指定元素，则添加指定元素。
更确切地讲，如果此 set 没有包含满足 (e==null ? e2==null : e.equals(e2)) 的元素 e2，则向此 set 添加指定的元素 e。
如果此 set 已包含该元素，则该调用不更改 set 并返回 false。
public class Solution {
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
int len = num.length;
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
HashSet<ArrayList<Integer>> tmp = new HashSet<ArrayList<Integer>>();
//Arrays.sort(num);
permutation(num, 0, len, result, tmp);
return result;
}
public void permutation(int[] num, int depth, int len,
ArrayList<ArrayList<Integer>> result, HashSet<ArrayList<Integer>> tmpResult){
if(depth == len){
ArrayList<Integer> per = new ArrayList<Integer>();
for(int i =0 ; i < len; i++)
per.add(num[i]);
if(tmpResult.add(per))
result.add(per);
}
for(int i = depth; i < len; i++) {
//if(i != depth && num[i] == num[depth])
// continue;
int tmp = num[i];
num[i] = num[depth];
num[depth] = tmp;
permutation(num, depth + 1, len, result, tmpResult);
tmp = num[i];
num[i] = num[depth];
num[depth] = tmp;
}
}
}