78. 子集

78. 子集

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
// LeetCode指定调用方法 
public List<List<Integer>> subsets(int[] nums) {

List<List<Integer>> result = new ArrayList<List<Integer>>();

// 循环依次求0、1、2、……、num.length个数的组合,这些组合就是它的子集
for (int i = 0; i <= nums.length; i++) {
combine(nums, result, new ArrayList<>(), 0, i);
}

return result;
}

// 求nums中选出k个数的所有组合
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);
}
}

学习所得,资料、图片部分来源于网络,如有侵权,请联系本人删除。

才疏学浅,若有错误或不当之处,可批评指正,还请见谅!


 
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×