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, i1, c, res) c c[:len(c)-1] } return }逐层拆解这个解法把“枚举所有子集”分解为两个正交的问题外层循环固定子集长度kk从0到len(nums)即分别枚举长度为 0、1、……、n 的所有子集。k 0时直接产出空集[]天然保证了空集被收录。内层generateSubsets用 DFS 枚举所有长度为k的子集参数start记录本轮搜索允许的起始下标递归时传i1确保每个子集内部下标严格递增——这正是“不重复选取同一元素”且“不产生排列顺序差异”的关键。几个值得注意的实现细节边界剪枝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 tmp1 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用tmp1 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{{}}的行为不同从源码结构看属于不同解法各自的选择后文测试用例会覆盖这一边界。三种解法对比维度解法一subsetsDFS解法二subsets1迭代解法三subsets2位运算输出顺序按子集长度升序按字典序元素顺序扩展按下标升序、长度交替去重/去排列机制start保证下标递增只向前扩展天然不回头每一位只取 0/1时间复杂度O(n·2^n)O(n·2^n)O(n·2^n)递归是深度 n否否空输入行为返回[][]int{{}}返回[][]int{{}}返回nil三者本质都是“对 2^n 个子集做完全枚举”只是枚举器分别用递归分层、幂集递推、二进制编号来表达。解法一的结构与仓库回溯专题中“Subset problems. Problem 78, Problem 90”归纳的模板一致选择/撤销/start指针三件套齐全这也是它能无缝推广到含重复元素的第 90 题的原因。测试验证运行与断言方式仓库为本题配有测试文件 leetcode/0078.Subsets/78. Subsets_test.go采用“参数结构体 答案结构体”的组织方式para78持有输入one []intans78持有期望输出one [][]intquestion78将两者聚合测试文件 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_Problem78L25-L48对每个用例打印输入输出并同时调用subsets、subsets1、subsets2三个实现保证三种解法在同一批用例下都能跑通。期望输出{[], {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}}正是解法一“按长度升序”的顺序印证了上文对其输出顺序的分析。运行方式上仓库根目录提供了 gotest.sh对全部题解包做带覆盖率统计的测试go test -covermodeatomic -coverprofilecoverage.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可以发现它在解法一的骨架上只加了两处改动入口先sort.Ints(nums)源码注释标注“这里是去重的关键逻辑”枚举循环内加入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无论哪条路径结果快照拷贝解法一/二的makecopy和不回头选取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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考