描述
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
1
2
3
4
5
6
7
| Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
|
分析
和上一题 Permutation 一样，求所有的排列，但单这道题给出的条件是集合中有重复的数字，我们需要做的是避免结果中有重复的排列，也就是在同一个位置的相同的取值，只在 nums 中取一次，也就是指枚举一次。在实现中，我们先将 nums 排序，这样相同的值就会在一次，对于相同的值，我们始终选择最靠右的没有被使用过的值，这样就能筛选掉重复的排列。
解决方案1(Java)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
backtrack(result, used, new ArrayList<>(), nums);
return result;
}
private void backtrack(List<List<Integer>> list, boolean[] used, List<Integer> nowList, int[] nums) {
if (nowList.size() == nums.length) {
list.add(new ArrayList<>(nowList));
} else {
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
if (i == nums.length - 1 || nums[i] != nums[i+1] || used[i+1]) {
nowList.add(nums[i]);
used[i] = true;
backtrack(list, used, nowList, nums);
used[i] = false;
nowList.remove(nowList.size()-1);
}
}
}
}
}
|
相关问题