题目
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
答案
Permutation II 只需要在Permutation的基础上，确保同一个位置i上如果已经选择了数字num, 则不能再次选择(use a set for this)
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
List<Integer> curr = new ArrayList<Integer>();
boolean[] used = new boolean[nums.length];
recur(nums, used, 0, curr, list);
return list;
}
private void recur(int[] nums, boolean[] used, int i, List<Integer> curr, List<List<Integer>> list) {
if(i == nums.length) {
list.add(new ArrayList<Integer>(curr));
return;
}
Set set = new HashSet<Integer>();
for(int j = 0; j < nums.length; j++) {
if(set.contains(nums[j])) continue;
if(!used[j]) {
set.add(nums[j]);
curr.add(nums[j]);
used[j] = true;
recur(nums, used, i + 1, curr, list);
used[j] = false;
curr.remove(curr.size() - 1);
}
}
}
}
