友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
78. Subsets
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
思路分析
这道题跟 90. Subsets II 类似。
-
一刷
-
二刷
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);
}
}