题目描述
给定一个可能具有重复数字的列表，返回其所有可能的子集
注意事项
- 子集中的每个元素都是非降序的
- 两个子集间的顺序是无关紧要的
- 解集中不能包含重复子集
样例
如果 S = [1,2,2]，一个可能的答案为：
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
思路
先将数组升序排序，将空集添加到结果集里。
排序后，从头开始遍历数组，每次访问一个元素，判断其是否重复
对于新元素i，这样处理：
- 访问结果集里的每个list，在其后添加i组成新的list加入到结果集（构造新的子集）
对于重复元素j，这样处理：
- 该元素的加入，新产生的子集个数为前一个元素产生的子集数
- 因为只有在前一个子集之后加入元素j组成的子集才是不在结果集里的！
- 为什么是前一个元素？因为提前给数组排序了，j元素一定与前一个元素相同！
- 访问结果集中的最后m个List（这些队列就是前一个元素添加到结果集的子集），在这些链表的末尾添加元素j，加入到结果集
新元素会对其之前的所有子集产生影响，重复元素只会影响前一个重复元素产生的新子集
代码
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
32
33
34
35
36
| public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) {
// write your code here
Arrays.sort(nums);
// 保存nums中不重复的元素
ArrayList<Integer> aList = new ArrayList<>();
// count[i]表示遍历到nums[i]时，新加入的子集个数
int[] count = new int[nums.length];
// 保存结果
ArrayList<ArrayList<Integer>> listHolder = new ArrayList<>();
// 预先加入空集
listHolder.add(new ArrayList<Integer>());
// 求非空集合
for(int i = 0; i < nums.length; i++) {
// 如果前面不存在该元素，取listHolder所有的list，在其后面加入该元素作为新的list加入到listHolder
if(!aList.contains(nums[i])) {
aList.add(nums[i]);
count[i] = listHolder.size();
for(int j = 0; j < count[i]; j++) {
ArrayList<Integer> list = new ArrayList<>(listHolder.get(j));
list.add(nums[i]);
listHolder.add(list);
}
}else { // 新子集只能通过在前一个元素新产生的子集后加入该元素来构造
int listHolderSize = listHolder.size();
count[i] = count[i-1];
for(int j = count[i]; j > 0; j--) {
ArrayList<Integer> list = new ArrayList<>(listHolder.get(listHolderSize - j));
list.add(nums[i]);
listHolder.add(list);
}
}
}
return listHolder;
}
|
考察点