题目要求
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
|
可以先参考关于SubsetI的这篇博客再看接下来的内容。
这里的区别在于假设输入的数组存在重复值，则找到所有不重复的子集。
思路一：链表的形式
我们可以通过例子[1，2，2，3]来说明。当我们遇到重复值时，我们可以使用一个临时数组将所有重复值的结果临时保存起来，在这道题目中就是[[2],[2,2]]，然后再将当前res中的结果和它一一组合成新的结果值，本例子中的当前res为[[ ],1]，这样合成之后就是[[],[2],[2,2],[1,2],[1,2,2]]，从而避免产生重复的结果。
代码如下：
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
| public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
result.add(new ArrayList<Integer>());
int length = nums.length;
Arrays.sort(nums);
for(int i = 0 ; i<length ; ){
LinkedList<List<Integer>> temp = new LinkedList<List<Integer>>();
for(List<Integer> tempResult : result){
List<Integer> copyTemp = new ArrayList<Integer>(tempResult);
copyTemp.add(nums[i]);
temp.add(copyTemp);
}
i++;
while(i<length && nums[i]==nums[i-1]){
int size = temp.size();
while(size-->0){
List<Integer> currentTemp = temp.removeFirst();
result.add(currentTemp);
List<Integer> moreCurrentTemp = new ArrayList<Integer>(currentTemp);
moreCurrentTemp.add(nums[i]);
temp.add(moreCurrentTemp);
}
}
result.addAll(temp);
}
return result;
}
|
思路二：递归
其实对于递归，应当考虑从递归的输入和输出考虑。在这里我们将递归的输入为当前的结果集，当前的数组，和遍历的起始下标。在递归中我们会将起始下标后的值依次加入当前结果集，并将结果集加入结果集数组中。如果遇到重复的数字，则继续遍历下一个数字，直至遍历结束。思路简单清晰，效率也很高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public List<List<Integer>> subsetsWithDup2(int[] nums) {
List<List<Integer>> fnl = new ArrayList<List<Integer>>();
Arrays.sort(nums);
helper(fnl, new ArrayList<Integer>(), nums, 0);
return fnl;
}
public void helper(List<List<Integer>> fnl, List<Integer> temp, int[] nums, int start){
fnl.add(new ArrayList<Integer>(temp));
for(int i =start; i<nums.length; i++){
if(i>start && nums[i]==nums[i-1]) continue;
temp.add(nums[i]);
helper(fnl, temp, nums, i+1 );
temp.remove(temp.size()-1);
}
}
|