78. 子集¶
题目¶
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入: nums = [1,2,3]
输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入: nums = [0]
输出: [[],[0]]
题解¶
Go
func subsets(nums []int) [][]int {
n := len(nums)
ans := make([][]int, 0, 1<<n) // 预分配空间
path := make([]int, 0, n) // 预分配空间
var dfs func(int)
dfs = func(i int) {
if i == n { // 子集构造完毕
ans = append(ans, slices.Clone(path)) // 复制 path
return
}
// 不选 nums[i]
dfs(i + 1)
// 选 nums[i]
path = append(path, nums[i])
dfs(i + 1)
path = path[:len(path)-1] // 恢复现场
}
dfs(0)
return ans
}
Python
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
path = []
n = len(nums)
def dfs(i: int) -> None:
if i == n: # 边界条件
ans.append(path.copy()) # copy, path[:]
return
dfs(i + 1) # 不选择 nums[i]
path.append(nums[i]) # 选择 nums[i]
dfs(i + 1)
path.pop() # 恢复
dfs(0)
return ans
复杂度¶
- 时间复杂度: \(O(n \ 2^n)\)，其中 \(n\) 为 \(nums\) 的长度。每次都是选或不选，递归次数为一个满二叉树的节点个数，那么一共会递归 \(O(2^n)\) 次（等比数列和），再算上加入答案时复制 path 需要 \(O(n)\) 的时间，所以时间复杂度为 \(O(n \ 2^n)\)。
- 空间复杂度: \(O(n)\)。