幂集
难度:
标签:
题目描述
Write a method to return all subsets of a set. The elements in a set are pairwise distinct.
Note: The result set should not contain duplicated subsets.
Example:
Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
代码结果
运行时间: 24 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 使用递归方法来生成所有子集。
* 2. 对于每个元素，有两种选择：包含在子集中或者不包含。
* 3. 使用Java Stream API来简化列表操作。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class SubsetsStream {
public List<List<Integer>> subsets(int[] nums) {
return subsetsHelper(nums, 0);
}
private List<List<Integer>> subsetsHelper(int[] nums, int index) {
if (index == nums.length) {
List<List<Integer>> base = new ArrayList<>();
base.add(new ArrayList<>());
return base;
}
int num = nums[index];
List<List<Integer>> subsets = subsetsHelper(nums, index + 1);
List<List<Integer>> moreSubsets = subsets.stream()
.map(ArrayList::new)
.peek(list -> list.add(num))
.collect(Collectors.toList());
return Stream.concat(subsets.stream(), moreSubsets.stream()).collect(Collectors.toList());
}
public static void main(String[] args) {
SubsetsStream solution = new SubsetsStream();
int[] nums = {1, 2, 3};
List<List<Integer>> subsets = solution.subsets(nums);
System.out.println(subsets);
}
}
解释
方法:
此题解采用了深度优先搜索（DFS）的方法来生成所有子集。函数`dfs`被设计为一个递归函数，其参数`i`表示当前考虑到的元素索引，而`r`是当前已构建的子集。在每个递归调用中，有两个选择：不包括当前元素，继续递归调用`dfs(i + 1, r)`；或者包括当前元素，在子集`r`中添加`nums[i]`，然后进行递归调用`dfs(i + 1, r + [nums[i]])`。当索引`i`等于数组长度时，意味着已经考虑了所有元素，当前子集`r`被添加到答案列表`ans`中。
时间复杂度:
O(2^n)
空间复杂度:
O(n)
代码细节讲解
🦆
在DFS递归函数中，如何确保生成的子集中不会包含重复元素，尤其是当输入数组已经保证无重复元素时？
▷🦆
为什么在到达数组长度的条件下（i == n），直接添加当前子集`r`到结果列表`ans`中，而不进行额外的检查或操作？
▷🦆
请解释递归调用`dfs(i + 1, r)`和`dfs(i + 1, r + [nums[i]])`在子集构建过程中的作用及其对结果集的影响。
▷