难度: Medium
幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。
示例:
输入： nums = [1,2,3] 输出： [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
Submission
运行时间: 24 ms
内存: 16.1 MB
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
def dfs(i, r):
if i == n:
ans.append(r)
return
dfs(i + 1, r)
dfs(i + 1, r + [nums[i]])
dfs(0, [])
return ans
Explain
此题解采用了深度优先搜索（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)
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums) # 数组的长度
ans = [] # 存储所有子集的结果列表
def dfs(i, r):
if i == n: # 如果i等于数组长度，说明所有元素都已考虑完毕
ans.append(r) # 将当前子集添加到结果列表中
return
dfs(i + 1, r) # 不包括当前元素的递归调用
dfs(i + 1, r + [nums[i]]) # 包括当前元素的递归调用
dfs(0, []) # 从第0个元素开始递归
return ans # 返回最终的所有子集列表
Explore
在提供的DFS递归方法中，确保不生成重复子集的关键在于输入数组`nums`本身不含重复元素，并且递归过程中对每个元素的处理是线性且顺序的。在每次递归调用中，函数要么选择包含当前元素，要么选择不包含，然后移动到下一个元素。由于每个元素在递归树的同一层只考虑一次，并且递归调用的顺序保证了每个子集都是独一无二的组合，这就避免了重复子集的生成。
当递归函数的索引`i`达到数组`nums`的长度`n`时，意味着所有元素都已被考虑完成。此时的子集`r`是根据之前的选择（包含或不包含每个元素）构建的一个完整子集。由于递归过程确保了每次递归都是基于不同的元素选择进行的，因此每到达这个终止条件，我们都得到了一个有效且不重复的子集，不需要进一步的检查或操作就可以直接将其加入到结果列表`ans`中。
在递归函数`dfs`中，`dfs(i + 1, r)`表示当前元素`nums[i]`不被包括在子集中，递归继续考虑下一个元素，这是构建所有可能子集的'不选'分支。而`dfs(i + 1, r + [nums[i]])`则表示当前元素`nums[i]`被包含在当前子集`r`中，然后递归继续考虑下一个元素，这是'选'分支。通过这两种路径，确保了从当前元素开始的所有可能的子集组合都被探索了，从而生成了包含所有可能元素组合的完整子集列表。这种方法有效地使用了分治策略，探索了所有包含或不包含每个特定元素的情况，从而得到了完整的幂集。