LeetCode-Go 实战：78. Subsets 的三种 Go 解法——DFS 枚举、迭代克隆与位运算幂集

LeetCode-Go 实战：78. Subsets 的三种 Go 解法——DFS 枚举、迭代克隆与位运算幂集

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇基于 LeetCode-Go 仓库中第 78 题 Subsets（子集/幂集）的题解文档，完整讲解该题的三种 Go 实现思路：按长度分层的 DFS 暴力枚举、逐元素扩展的迭代克隆法、以及基于二进制掩码的位运算枚举。读完后你将理解每种解法的核心不变量、边界剪枝细节与去副本技巧，并知道如何在仓库中运行测试验证这三种解法的正确性，同时了解它与第 90 题（含重复元素）的衔接关系。

题目描述

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

注意：解集不能包含重复的子集。

示例（摘自题解文档 website/content.en/ChapterFour/0001~0099/0078.Subsets.md）：

输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

注意[]（空集）也算一个子集，所以n个元素的集合共有2^n个子集——这正是“幂集（power set）”名称的由来。

解题思路

题解文档给出的总体策略是：找出集合中的所有子集，空集也算子集；数组中的数字不会重复，因此可以直接用DFS 暴力枚举，无需去重。文档同时指出，本题与 第 90 题 Subsets II 和 第 491 题 Non-decreasing Subsequences 类似，可以放在一起解答和复习——90 题是多出“元素可能重复”这一约束，解法一里预留的start分层结构正好成为去重的挂载点（后文展开）。

仓库实现文件 leetcode/0078.Subsets/78. Subsets.go 中提供了三种解法：subsets（解法一，DFS）、subsets1（解法二，迭代克隆）、subsets2（解法三，位运算）。下面逐一剖析。

解法一：按长度分层的 DFS 枚举

核心代码

// 解法一 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 }

逐层拆解

这个解法把“枚举所有子集”分解为两个正交的问题：

1. 外层循环固定子集长度k：k从0到len(nums)，即分别枚举长度为 0、1、……、n 的所有子集。k = 0时直接产出空集[]，天然保证了空集被收录。
2. 内层generateSubsets用 DFS 枚举所有长度为k的子集：参数start记录本轮搜索允许的起始下标，递归时传i+1，确保每个子集内部下标严格递增——这正是“不重复选取同一元素”且“不产生排列顺序差异”的关键。

几个值得注意的实现细节：

• 边界剪枝：for i := start; i < len(nums)-(k-len(c))+1; i++。循环上界不是简单的len(nums)，而是n - (k - len(c)) + 1，含义是：当前已经选了len(c)个，还差k - len(c)个才能凑齐长度k，因此i最大只能走到还剩刚好足够元素的位置，避免无谓的空递归。源码中对应的注释// i will at most be n - (k - c.size()) + 1即为此意。
• 必须拷贝再入栈：命中len(c) == k时，c是递归全程复用的同一块底层数组，直接append(*res, c)会导致所有结果指向同一份被后续回溯污染的数据。解法用b := make([]int, len(c)); copy(b, c)先复制一份快照再存入结果。
• 回溯退格：c = c[:len(c)-1]把最后一个元素“撤销”，恢复现场后进入下一个i，这是标准回溯三件套（选择、递归、撤销选择）中的撤销步骤。
• 结果顺序：由于外层按k从小到大展开，解法一的输出是[[], [1], [2], ..., [1,2], ..., [1,2,3]]这种“按长度升序”的确定性顺序——这一点在测试用例中有直接体现（见后文）。

时间复杂度为 O(n·2^n)（共 2^n 个子集，每个子集平均长度 n/2），空间复杂度除结果外为 O(n) 的递归栈深度。

解法二：迭代克隆，逐元素扩展幂集

核心代码

// 解法二 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 }

原理：动态增长的幂集

解法二不用递归，而是利用一条幂集构造的递推性质：S(i) = S(i-1) ∪ {x ∪ {nums[i]} | x ∈ S(i-1)}，即“加入新元素 nums[i] 后的幂集 = 原有幂集 + 原有每个子集各自追加 nums[i]”。

实现上有几个精巧之处：

• res := make([][]int, 1)初始化一个只有一个空槽位（零值 nil 切片）的切片，等价于初始幂集{[]}。
• 内层for _, org := range res遍历的是res的遍历快照范围：Go 的range在开始时确定切片长度，因此即使内层不断append到res，本轮也只会遍历“进入本轮之前已存在的子集”，恰好实现“每个旧子集只扩展一次”。若误写成for i := 0; i < len(res); i++的形式，就会把新扩展出的子集再次扩展，直接算错。
• clone := make([]int, len(org), len(org)+1)预留了 1 个容量，避免append时重新分配内存。
• sort.Ints(nums)对输入排序。由于幂集元素本身无序，排序只是让结果按字典序整齐输出，不影响正确性。

以nums = [1, 2, 3]走一遍：初始{[]}→ 处理 1 得{[], [1]}→ 处理 2 得{[], [1], [2], [1,2]}→ 处理 3 得 8 个子集。每一轮结果规模恰好翻倍，与 2^n 的总数吻合。

解法三：位运算掩码枚举

核心代码

// 解法三：位运算的方法 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 }

原理：把子集编号当作二进制

n 个元素的集合，其子集与0到2^n - 1这 2^n 个整数的二进制表示一一对应：第j位为 1 表示选取nums[j]。因此：

• sum := 1 << uint(len(nums))计算子集总数2^n；
• 外层i枚举“子集编号”，内层tmp := i逐位右移tmp >>= 1，用tmp&1 == 1判断该位是否为 1；
• 内层循环j从len(nums)-1递减到 0，配合stack = append([]int{nums[j]}, stack...)的头部插入写法，最终stack保持nums原有的下标顺序（升序）。

这里有个类型细节：1 << uint(len(nums))的移位量显式转成了uint——len()返回int，而移位操作的右操作数需要无符号整型，这种写法在 32 位与 64 位平台上行为一致，是 Go 中的良好习惯。LeetCode-Go 的位运算专题文档也将此类“用二进制编号枚举组合”的手法归入位运算的典型应用。

此外注意len(nums) == 0时返回nil的分支——这与解法一/解法二对空输入返回[][]int{{}}的行为不同，从源码结构看属于不同解法各自的选择（后文测试用例会覆盖这一边界）。

三种解法对比

三者本质都是“对 2^n 个子集做完全枚举”，只是枚举器分别用递归分层、幂集递推、二进制编号来表达。解法一的结构与仓库回溯专题中“Subset problems. Problem 78, Problem 90”归纳的模板一致：选择/撤销/start指针三件套齐全，这也是它能无缝推广到含重复元素的第 90 题的原因。

测试验证：运行与断言方式

仓库为本题配有测试文件 leetcode/0078.Subsets/78. Subsets_test.go，采用“参数结构体 + 答案结构体”的组织方式：para78持有输入one []int，ans78持有期望输出one [][]int，question78将两者聚合（测试文件 L8-L23）。测试用例有两组：

{ para78{[]int{}}, ans78{[][]int{{}}}, }, { para78{[]int{1, 2, 3}}, ans78{[][]int{{}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}}}, },

其中Test_Problem78（L25-L48）对每个用例打印输入输出，并同时调用subsets、subsets1、subsets2三个实现，保证三种解法在同一批用例下都能跑通。期望输出{[], {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}}正是解法一“按长度升序”的顺序，印证了上文对其输出顺序的分析。

运行方式上，仓库根目录提供了 gotest.sh，对全部题解包做带覆盖率统计的测试：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

也可以只跑本题所在包，查看三种解法的实际输出：

go test -v -run Test_Problem78 ./leetcode/0078.Subsets/

延伸：从第 78 题到第 90 题的去重推广

题解文档明确提示本题与第 90 题（Subsets II，数组可能含重复元素）一起复习。对比 leetcode/0090.Subsets-II/90. Subsets II.go 的generateSubsetsWithDup可以发现，它在解法一的骨架上只加了两处改动：

1. 入口先sort.Ints(nums)，源码注释标注“这里是去重的关键逻辑”；
2. 枚举循环内加入if i > start && nums[i] == nums[i-1] { continue }，注释解释为“本次不取重复数字，下次循环可能会取重复数字”。

这一句剪枝正是利用了解法一“同一层内start划分同级候选”的结构：同一层中相等的相邻元素只允许取第一个，从而从源头消灭重复子集。这也解释了为什么解法一要特意保留start参数——它在 78 题中只负责防止下标回退，到了 90 题则升级去了重的判定基准。至于第 491 题，则要求子集保持非递减顺序，同样可以复用同一套枚举骨架，作为本文的后续练习方向。

小结

• 第 78 题的本质是枚举 2^n 个子集，仓库给出三条等价的实现路径：DFS 分层（subsets）、幂集递推（subsets1）、二进制掩码（subsets2），实现见 leetcode/0078.Subsets/78. Subsets.go；
• 无论哪条路径，结果快照拷贝（解法一/二的make+copy）和不回头选取（start递增 / 掩码只读）是保证结果正确且无重复的两大关键；
• 用gotest.sh或单包go test即可验证三种解法；
• 掌握解法一的start分层结构后，向第 90 题的排序+剪枝去重推广只有一步之遥。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go