难度: Medium
给定一个整数数组 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] <= 10nums 中的所有元素 互不相同注意：本题与主站 78 题相同： https://leetcode-cn.com/problems/subsets/
运行时间: 22 ms
内存: 16.2 MB
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(i, path):
if i >= len(nums):
res.append(list(path))
return
dfs(i+1, path)
path.append(nums[i])
dfs(i+1, path)
path.pop()
dfs(0, [])
return res
此题解采用深度优先搜索（DFS）的方式来生成所有可能的子集。递归函数`dfs`接受两个参数，`i`表示当前考虑到的数组元素索引，`path`表示当前构建的子集。每次递归调用有两个选择：不包含当前元素，或包含当前元素。当索引`i`超过数组长度时，将当前路径`path`添加到结果列表`res`中，这表示一个完整的子集已形成。递归过程中，先进行一次递归以跳过当前元素（即不将其加入到当前子集中），然后将元素加入`path`进行另一次递归调用，之后再将其移除以恢复状态，以便回溯。
时间复杂度: O(n * 2^n)
空间复杂度: O(n * 2^n)
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(i, path):
# 当前索引超出数组长度，将当前路径作为一个子集添加到结果中
if i >= len(nums):
res.append(list(path))
return
# 不包含当前元素的递归
dfs(i+1, path)
# 包含当前元素的递归
path.append(nums[i])
dfs(i+1, path)
# 回溯，移除最近添加的元素
path.pop()
# 从索引0开始递归
dfs(0, [])
return res
在递归函数中，先进行'不包含当前元素'的递归调用，是为了确保子集生成的顺序是按照一定的规律进行的。具体来说，这种顺序可以保证先生成较小元素数量的子集，然后逐渐增加元素数量。例如，先生成[]，然后生成[1]，再生成[1, 2]等。如果先进行'包含当前元素'的递归调用，则生成的子集顺序会首先是包含更多元素的子集，例如，先生成[1, 2, 3]，再生成[1, 2]。虽然这不影响子集的完整性，但会改变子集的排列顺序。因此，两种顺序都是正确的，选择哪种取决于你想得到的子集列表的顺序。
在递归函数中执行回溯操作，即移除最近添加的元素，是为了恢复到递归调用之前的状态。这样做的目的是为了在递归的不同分支中复用'path'列表。当递归调用返回时，需要确保'path'没有被前一个递归分支修改过，这样才能保证每个子集都是正确构造的。此外，回溯是深度优先搜索（DFS）算法中的一个重要步骤，它允许我们探索所有可能的解决方案而不会造成干扰。
递归终止条件'if i >= len(nums)'表示当当前索引'i'超出了输入数组'nums'的长度时，递归应该停止。这个条件是必要的，因为它标志着所有数组元素都已经被考虑过，当前的'path'列表代表了一种可能的子集。如果没有这个终止条件，递归将无法正确结束，可能会导致索引越界错误。此外，这个条件确保了每次递归都对数组中的一个元素进行决策，直到所有元素都被考虑过，从而生成所有可能的子集。