友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
-
1 <= nums.length <= 10 -
-10 <= nums[i] <= 10 -
nums中的所有元素 互不相同
思路分析
这道题跟 90. 子集 II 类似：使用 Subsets 子集 模式即可轻松解决。
以空集为起点，每次都在已有子集后面添加新元素来构建新的子集。处理完所有元素时，就生成了全部子集。
如果元素中有重复元素，那么就需要先对元素排序，遇到重复元素时，就不能对虽有已有元素都添加新元素了（因为前一个元素重复，那么对全部已有元素添加新元素就会有重复自己）。只需要针对上一次新添加的子集添加新元素即可，依次执行，直到有不重复元素则再次恢复成从全部子集添加元素。
-
一刷
-
二刷
-
三刷
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
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Subsets.
*
* Memory Usage: 37.1 MB, less than 99.18% of Java online submissions for Subsets.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-02 19:56
*/
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>());
for (int num : nums) {
List<List<Integer>> newSubsets = new ArrayList<>();
for (List<Integer> current : result) {
ArrayList<Integer> integers = new ArrayList<>(current);
integers.add(num);
newSubsets.add(integers);
}
result.addAll(newSubsets);
}
return result;
}
/**
* Runtime: 74 ms, faster than 5.06% of Java online submissions for Subsets.
*
* Memory Usage: 50.3 MB, less than 5.74% of Java online submissions for Subsets.
*/
public List<List<Integer>> subsetsLevel(int[] nums) {
if (Objects.isNull(nums) || nums.length == 0) {
return Collections.emptyList();
}
Set<Set<Integer>> subsets = new HashSet<>();
subsets.add(Collections.emptySet());
for (int i = 0; i < nums.length; i++) {
ArrayList<Set<Integer>> list = new ArrayList<>(subsets);
list.forEach(s -> {
for (int num : nums) {
Set<Integer> set = new TreeSet<>(s);
set.add(num);
subsets.add(set);
}
});
}
List<List<Integer>> result = subsets.stream()
.map(ArrayList::new)
.collect(Collectors.toList());
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-08 21:15:30
*/
public List<List<Integer>> subsets(int[] nums) {
if (nums == null || nums.length == 0) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, result, new ArrayList<Integer>());
return result;
}
private void backtrack(int[] nums, int start,
List<List<Integer>> result, List<Integer> subset) {
result.add(new ArrayList<>(subset));
for (int i = start; i < nums.length; i++) {
subset.add(nums[i]);
backtrack(nums, i + 1, result, subset);
subset.remove(subset.size() - 1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-16 20:09:31
*/
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>(1 << nums.length);
result.add(new ArrayList<>());
for (int num : nums) {
int size = result.size();
for (int i = 0; i < size; i++) {
List<Integer> existed = result.get(i);
List<Integer> adding = new ArrayList<>(existed);
adding.add(num);
result.add(adding);
}
}
return result;
}