Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
题意：
打印全排列，注明了给定序列可含有重复元素
Solution1: Backtracking
code
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> path = new ArrayList<>();
Arrays.sort(nums); // necessary！因为后面要查重
dfs(list, path, nums, new boolean[nums.length]);
return list;
}
private void dfs(List<List<Integer>> list, List<Integer> path, int [] nums, boolean [] used){
if(path.size() == nums.length){
list.add(new ArrayList<>(path));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
used[i] = true; //标记用过
path.add(nums[i]);
dfs(list, path, nums, used);
used[i] = false; //恢复default值
path.remove(path.size() - 1);
}
}
}