力扣 78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
方案一：递归，遍历每一种可能。
func subsets(nums []int) (ans [][]int) {
// 当前选中的数组
chosen := make([]int, 0, len(nums))
// 定义递归函数，i 为数组下标
var recur func(i int)
recur = func(i int) {
// 如果数组下标等于数组长度
if i == len(nums) {
// 定义临时数组，使用深拷贝将 chosen 的内容拷贝到临时数组
tmp := make([]int, len(chosen))
copy(tmp, chosen)
// 直接 append chosen 会有问题，因为 chosen 是引用类型
// 会导致 ans 里存放的都是 chosen 的引用
ans = append(ans, tmp)
return
}
// 每个元素都有两种可能，加入结果数组，或者不加入结果数组
// 不选当前元素，递归到下一轮
recur(i + 1)
// 选中当前元素，递归到下一轮
chosen = append(chosen, nums[i])
recur(i + 1)
// 还原现场，因为当前递归分支的选择不应该影响隔壁分支
chosen = chosen[:len(chosen) - 1]
// [] 初始 什么都不选
// [] [1] 是否选择 1
// [] [2] [1] [1,2] 是否选择 2
// [] [3] [2] [2,3] [1] [1,3 ] [1,2] [1,2,3] 是否选择 3
}
recur(0)
return
}
- 时间复杂度：O(n * 2^n)，因为一共有 2^n 个状态，每个状态需要 O(n) 的时间复杂度（深拷贝），所以时间复杂度为 O(n * 2^n)。
- 空间复杂度：O(n)，因为栈深度为 n，chosen 数组长度不超过 n，所以空间复杂度为 O(n)。