leetcode 90. 子集 II
题目：90. 子集 II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明:
解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
方法：Backtracking（回溯）
思路：Backtracking（回溯），将求子集问题转化成求所有可能的组合问题（循环依次求0、1、2、……、num.length个数的组合，这些组合就是它的子集），通过回溯求组合。可参考letecode 78. 子集。通过事先对nums排序，在回溯递归选取元素时，如果当前选取元素是同层递归的非第一选取元素且与在nums中的前一个元素相等时，直接跳过该元素的选取。
运行数据：执行用时：1 ms，内存消耗：40 MB
复杂度分析：
- 时间复杂度：O(n * 2^n)，n为nums中元素的个数，生成所有子集的时间复杂度O(2^n)，复制到输出集合中的时间复杂度O(n)。
- 空间复杂度：O(n * 2^n)，n为nums中元素的个数，存储所有子集，共 n 个元素，每个元素都有可能存在或者不存在。
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
|
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (int i = 0; i <= nums.length; i++) {
combine(nums, result, new ArrayList<>(), 0, i);
}
return result;
}
private void combine(int[] nums, List<List<Integer>> result, List<Integer> subsetsList, int t, int k) {
if (k == 0) {
result.add(new ArrayList<>(subsetsList));
return ;
}
for (int i = t; i <= nums.length - k; i++) {
if (i > t && nums[i] == nums[i - 1]) {
continue;
}
subsetsList.add(nums[i]);
combine(nums, result, subsetsList, i + 1, k - 1);
subsetsList.remove(subsetsList.size() - 1);
}
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
