题目
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
1
2
3
4
5
| 输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
|
示例 2：
1
2
| 输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
|
1
2
3
| 提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
|
思路
也是一个全拍列组合，但是我们如果使用46题的全排列组合会产生重复的数据，所以需要先对数组进行排序，这个是一贯思路，只要排除重复大部分情况下的组合都是通过前排序，然后和前一个数对比实现去重
实现
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
29
30
31
| private static class Solution {
boolean[] used;
Deque<Integer> col = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
used = new boolean[nums.length];
dfs(nums);
return res;
}
private void dfs(int[] nums) {
if (col.size() == nums.length) {
res.add(new ArrayList<>(col));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
col.add(nums[i]);
used[i] = true;
dfs(nums);
col.removeLast();
used[i] = false;
}
}
}
|
