LeetCode-Go 题解 78Subsets 子集问题三种解法DFS、迭代、位运算深入剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读LeetCode 78. Subsets 是回溯与 DFS 家族中最经典的入门题目给定一组不含重复元素的整数数组返回其全部子集幂集。本文以 LeetCode-Go 仓库中 leetcode/0078.Subsets 的实现为主线完整讲解题面、三种可运行解法DFS 回溯、迭代构造、位运算枚举的源码级原理与复杂度并延伸到第 90 题含重复元素和第 491 题的变体对比。读完本文你将掌握“枚举组合/子集”这一类题目的通用模板并能直接复用仓库中的可测试代码。题目返回幂集且不重不漏原题要求见 READMEGiven a set ofdistinctintegers, nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets.即输入一个不含重复元素的整数数组nums返回该数组所有可能的子集幂集且解集中不能出现重复子集。官方示例Input: nums [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]注意几点边界语义空集[]也是合法子集必须出现在答案中子集内部与子集之间的顺序不要求与输入一致因此[1,3]与[3,1]属于同一个子集解集中只需保留一种数组元素互不相同这是“不需要去重”的前提也是与第 90 题的本质差异。解法一DFS 回溯暴力枚举仓库主推方案仓库 78. Subsets.go 中subsets与generateSubsets构成了标准的 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 }执行流程拆解外层for k : 0; k len(nums); k枚举子集的长度从 0空集一直到n全集内层递归generateSubsets(nums, k, 0, c, res)负责在nums中按下标递增的顺序挑出长度为k的组合终止条件len(c) k命中后先把c拷贝一份再追加进结果——这是关键c是共享切片后续回溯会复用并修改它直接append(*res, c)会导致结果互相污染i1保证每次选择的起点向后推进避免选中自身、天然形成组合而非排列因此不会产生[1,2]与[2,1]这样的重复。代码中循环上界写成了len(nums)-(k-len(c))1这是对“剩余元素必须足够填满剩余名额”的剪枝当前已选len(c)个还需k-len(c)个所以i最多只能取到n-(k-len(c))该剪枝让递归树提前收窄减少无效分支。去掉这层剪枝、直接写i len(nums)逻辑同样正确只是会多走若干注定无法凑满k的分支。以 nums [1,2,3] 为例k 0直接产出[]k 1依次产出[1]、[2]、[3]k 2产出[1,2]、[1,3]、[2,3]k 3产出[1,2,3]。合计 8 个正是2^3个幂集元素。解法二迭代构造增量扩展仓库 78. Subsets.go 中subsets1给出了一种非递归的增量思路// 解法二 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 }原理初始res [[]]只含空集每读入一个新元素nums[i]就遍历当前res中已有的全部子集把每个子集拷贝一份并追加该元素再放回res循环结束后res即为完整幂集。clone : make([]int, len(org), len(org)1)预先分配了len(org)1的容量避免append触发多次扩容是仓库中刻意为之的小优化。以 nums [1,2,3] 为例步骤读入元素新增子集res 规模初始——1[]11[1]222[2]、[1,2]433[3]、[1,3]、[2,3]、[1,2,3]8可以看到每轮规模翻倍最终恰好得到2^n个子集。该方案还额外调用了sort.Ints(nums)虽然本题元素互不相同、排序并非必需但为复用该模板处理含重复元素的变体保留了习惯见下文第 90 题。解法三位运算枚举000…0 到 111…1仓库 78. Subsets.go 中subsets2把“是否选取某个元素”建模成二进制位// 解法三位运算的方法 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的数组共有2^n个子集恰好与n位二进制数一一对应i从0000...000递增到2^n-1111...111第j位为 1 表示选取nums[j]内层循环从低位到高位逐位判断并把选中的元素头插到stack前部从而维持与nums一致的顺序注意len(nums) 0时直接返回nil的早退分支这是与另两种解法的边界差异subsets与subsets1对空数组返回[[]]包含空集而subsets2返回nil。三者在 LeetCode 判题语义下等价但在单元测试中表现不同见下文测试小节。位运算方案的优势是不需要递归栈、不需要剪枝推导时间复杂度同样是O(n·2^n)且便于用整数直接表达“选/不选”的完整状态空间是理解状态压缩 DP如旅行商问题、子集枚举类题目的良好铺垫。测试与验证仓库中的单元测试仓库 78. Subsets_test.go 采用 LeetCode-Go 仓库统一的question/para/ans测试骨架包含两组用例qs : []question78{ { para78{[]int{}}, ans78{[][]int{{}}}, }, { para78{[]int{1, 2, 3}}, ans78{[][]int{{}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}}}, }, }空数组输入对应输出[[]]印证“空集也是子集”的题意[1,2,3]对应 8 个子集验证subsets、subsets1、subsets2三种实现均被调用并运行测试文件第 44-46 行。仓库根目录的 gotest.sh 展示了如何为整个leetcode包跑测试并生成统一覆盖率文件go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...读者可把./leetcode/...换成./leetcode/0078.Subsets定向运行本题测试go test -v ./leetcode/0078.Subsets变体延伸第 90 题与第 491 题原 README 明确提示“这一题和第 90 题、第 491 题类似可以一起解答和复习”这是 LeetCode-Go 仓库按题型归组刷题的设计思路。90. Subsets II数组可能包含重复元素第 90 题题面见 leetcode/0090.Subsets-II/README.md数组可能含重复元素仍要求返回不重复的幂集例如[1,2,2]的输出不能出现两个[2]或两个[1,2]。仓库解法 90. Subsets II.go 与 78 题共用同一 DFS 骨架只增加两处关键逻辑sort.Ints(nums) // 这里是去重的关键逻辑 ... if i start nums[i] nums[i-1] { // 这里是去重的关键逻辑,本次不取重复数字下次循环可能会取重复数字 continue }先排序让相等的元素相邻是“同层剪枝”的前提在同一层递归i start中若当前元素与前一元素相同则跳过同一深度上选择nums[i]与选择nums[i-1]会生成完全相同的子集前缀必须剪掉而不同深度即后续递归仍可取重复数字因此[2,2]这样的子集得以保留。可见78 题是“无重枚举”的基线模板90 题只需在模板上叠加“排序 同层相等跳过”即可完成去重。491. Non-decreasing Subsequences不排序的同类去重leetcode/0491.Non-decreasing-Subsequences 要求返回所有非递减子序列且不能重复——但它不允许先排序子序列必须保持原数组相对顺序因此去重手段从“相邻相等跳过”改为在每层递归内用哈希集合记录“本层已选过哪些值”属于对 78 题模板的进阶改造。三题连刷可以完整覆盖“组合枚举”从无重到有重的全部去重套路。复杂度总结与选型建议三种解法的时间复杂度均为O(n·2^n)每个子集平均长度为O(n)共2^n个子集空间复杂度O(n·2^n)用于存储结果不含结果时为递归栈O(n)。解法核心思想是否递归备注subsets解法一DFS 回溯 长度枚举 剪枝是最通用可直接改造为 90/491 题subsets1解法二迭代增量扩展否代码最简、不易出错subsets2解法三位运算枚举 0…2ⁿ-1否贴近状态压缩思路空数组返回 nil实战建议面试中首选 DFS 回溯模板因为它的递归树可视化程度高、便于讲解且去重扩展90 题与子序列扩展491 题都是同一模板的小改动需要快速 AC 时迭代构造最稳妥想展示对状态空间的理解时再补充位运算方案。参考资料题目说明与思路 leetcode/0078.Subsets/README.md三种解法实现leetcode/0078.Subsets/78. Subsets.go单元测试leetcode/0078.Subsets/78. Subsets_test.go含重复元素的变体leetcode/0090.Subsets-II非递减子序列变体leetcode/0491.Non-decreasing-Subsequences全量测试命令gotest.sh【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
