难度: 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 中的所有元素 互不相同运行时间: 44 ms
内存: 15.2 MB
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
def backtrack(path, start):
result.append(list(path))
if len(path) >= len(nums):
return
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(path, i+1)
path.pop()
backtrack([], 0)
return result
这个题解使用回溯算法来生成所有可能的子集。主要思路是：从空集开始，依次考虑数组中的每个元素，可以选择将当前元素加入子集，也可以不加入，然后递归地继续处理剩余元素，直到处理完所有元素。在回溯过程中，通过维护一个路径数组 path 来记录当前子集，并在每次递归时将当前路径加入结果集中。通过回溯的方式，可以生成所有可能的子集组合。
时间复杂度: O(n * 2^n)
空间复杂度: O(2^n)
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
def backtrack(path, start):
# 将当前路径加入结果集
result.append(list(path))
# 如果当前路径长度已经等于数组长度，停止递归
if len(path) >= len(nums):
return
# 从 start 开始，选择每个元素是否加入当前路径
for i in range(start, len(nums)):
path.append(nums[i]) # 选择当前元素
backtrack(path, i+1) # 递归处理剩余元素
path.pop() # 回溯，移除当前元素
backtrack([], 0)
return result
这个递归停止条件实际上并不是必要的。在生成所有子集的问题中，递归的主要目的是考虑所有可能的元素组合，而不是达到某个特定的路径长度。递归自然会在遍历完所有元素后停止，因为没有更多元素可以选择或排除。因此，这一条件可以省略，简化代码的逻辑。
将当前的路径复制并添加到结果集中确实会增加时间和空间复杂度，因为每次递归都需要创建一个新的列表。一种更优的方法是使用全局结果集，在递归的每个阶段添加当前路径的引用，但随后在每次递归返回前恢复路径的原始状态（即回溯）。这种方法可以减少内存的使用，因为不需要频繁地创建和销毁列表，但需要在输出结果之前将所有子集复制出来，以避免最终结果中只有对同一列表的引用。
`start`参数用于控制每次递归从数组的哪个位置开始考虑元素，以避免生成重复的子集。通过设置`start`为`i+1`，我们确保了在递归的每一层中不会重新考虑之前已经被选择的元素，从而可以生成所有不同的子集。这个处理保证了每个元素在子集中只出现一次，并且子集的生成过程中不会有重复。
`path.pop()`操作是回溯算法中的核心，用于撤销上一步执行的操作，确保路径(path)可以回到上一个状态，进而进行新的选择。这样，每次递归返回后，当前路径会回到未选择最后一个元素的状态，然后可以选择不同的元素加入路径或者继续回溯。这保证了所有可能的子集都可以通过不同的路径选择被遍历到并生成。