子集

怎样从“nums=[1,2,3],返回所有子集。”推导出 回溯 · 子集，并证明每次状态变化都不会漏掉答案？

中心结论：选/不选回溯:每层 skip 或 take;index===n 收集;必须 path.pop 撤销。

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

在本站主例中，nums=[1,2,3],返回所有子集。

算法最终需要得到或观察：8 个子集含空集。

先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“选择树与撤销绳”，明确答案需要观察什么。
2. 2状态只维护 index、path、res、决策树节点。
3. 3转移每一步按照 选/不选回溯:每层 skip 或 take;index===n 收集;必须 path.pop 撤销。
4. 4收尾读取 8 个子集含空集。，并复核边界与复杂度。

路径记录已做选择，候选集合决定下一步，撤销保证兄弟分支互不污染。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：index、path、res、决策树节点。

找出一个集合中的所有子集，空集也算是子集。且数组中的数字不会出现重复。用 DFS 暴力枚举即可。 这一题和第 90 题，第 491 题类似，可以一起解答和复习。

选/不选回溯:每层 skip 或 take;index===n 收集;必须 path.pop 撤销。

执行过程中持续维护：index、path、res、决策树节点。

正确性依赖以下不变量：每个元素恰好在某条路径上被决定选或不选一次。；res.push 必须复制 path;take 后必须 pop。

面试时可以压缩为：选/不选 dfs:先 skip 再 take+pop;共 2^n 条路径;时间 O(n·2^n)。

落到当前题，执行机制可以压缩为：选/不选回溯:每层 skip 或 take;index===n 收集;必须 path.pop 撤销。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums=[1,2,3],返回所有子集。 因为：选/不选回溯:每层 skip 或 take;index===n 收集;必须 path.pop 撤销。
2. 2收集子集 []每个递归入口都对应一个子集。 因为：不跳过任何中间状态。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4选择 nums[1]=2做选择,深入。 因为：start=i+1 避免重复组合。
5. 5选择 nums[2]=3做选择,深入。 因为：start=i+1 避免重复组合。
6. 6撤销 3,回到上一层恢复状态,尝试不选分支。 因为：回溯必须撤销选择。
7. 7选择 nums[2]=3做选择,深入。 因为：start=i+1 避免重复组合。
8. 8收尾与复杂度8 个子集含空集。 因为：时间 O(n · 2^n) · 空间 O(n)。选/不选回溯:每层 skip 或 take;index===n 收集;必须 path.pop 撤销。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import "sort"

// 解法一
func subsets(nums []int) [][]int {
	c, res := []int{}, [][]int{}
	for k := 0; k <= len(nums); k++ {
		generateSubsets(nums, k, 0, c, &res)
	}
	return res
}

func generateSubsets(nums []int, k, start int, c []int, res *[][]int) {
	if len(c) == k {
		b := make([]int, len(c))
		copy(b, c)
		*res = append(*res, b)
		return
	}
	// i will at most be n - (k - c.size()) + 1
	for i := start; i < len(nums)-(k-len(c))+1; i++ {
		c = append(c, nums[i])
		generateSubsets(nums, k, i+1, c, res)
		c = c[:len(c)-1]
	}
	return
}

// 解法二
func subsets1(nums []int) [][]int {
	res := make([][]int, 1)
	sort.Ints(nums)
	for i := range nums {
		for _, org := range res {
			clone := make([]int, len(org), len(org)+1)
			copy(clone, org)
			clone = append(clone, nums[i])
			res = append(res, clone)
		}
	}
	return res
}

// 解法三：位运算的方法
func subsets2(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}
	res := [][]int{}
	sum := 1 << uint(len(nums))
	for i := 0; i < sum; i++ {
		stack := []int{}
		tmp := i                              // i 从 000...000 到 111...111
		for j := len(nums) - 1; j >= 0; j-- { // 遍历 i 的每一位
			if tmp&1 == 1 {
				stack = append([]int{nums[j]}, stack...)
			}
			tmp >>= 1
		}
		res = append(res, stack)
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="subsets", nums=[1,2,3]
    //    期望：8 个子集含空集。
    //
    // 2. 失败 / 未命中
    //    检查：res.push(path) 未复制会污染结果。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC90 子集 II；LC77 组合
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums=[1,2,3],返回所有子集。
2. 2重复先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。
3. 3优化选/不选回溯:每层 skip 或 take;index===n 收集;必须 path.pop 撤销。
4. 4证明每个元素恰好在某条路径上被决定选或不选一次。；res.push 必须复制 path;take 后必须 pop。
5. 5复杂度时间 O(n · 2^n)，空间 O(n)