leetcode 78. 子集
题目：78. 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明:
解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
方法：Backtracking（回溯）
思路：Backtracking（回溯），将求子集问题转化成求所有可能的组合问题（循环依次求0、1、2、……、num.length个数的组合，这些组合就是它的子集），通过回溯求组合。可参考letecode 77. 组合。
运行数据：执行用时：1 ms，内存消耗：40.4 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
|
public List<List<Integer>> subsets(int[] 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++) {
subsetsList.add(nums[i]);
combine(nums, result, subsetsList, i + 1, k - 1);
subsetsList.remove(subsetsList.size() - 1);
}
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
