题目
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
思路
和全排列II一个思路，先排序后去重
实现
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
| private static class Solution {
boolean[] used;
Deque<Integer> col = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
used = new boolean[nums.length];
Arrays.sort(nums);
dfs(nums, 0);
return res;
}
private void dfs(int[] nums, int cur) {
res.add(new ArrayList<>(col));
for (int i = cur; 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, i + 1);
used[i] = false;
col.removeLast();
}
}
}
|
