企业官网建设流程全解析

LeetCode-Go 题解 78：Subsets 子集问题，三种解法（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 题的变体对比。读完本文，你将掌握“枚举组合/子集”这一类题目的通用模板，并能直接复用仓库中的可测试代码。

题目：返回幂集且不重不漏

原题要求（见 README）：

Given 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, i+1, 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)会导致结果互相污染；
• i+1保证每次选择的起点向后推进，避免选中自身、天然形成组合而非排列，因此不会产生[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] 为例

可以看到每轮规模翻倍，最终恰好得到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 tmp&1 == 1 { stack = append([]int{nums[j]}, stack...) } tmp >>= 1 } res = append(res, stack) } return res }

原理

• 长度为n的数组共有2^n个子集，恰好与n位二进制数一一对应；
• i从0（000...000）递增到2^n-1（111...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 -covermode=atomic -coverprofile=coverage.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)）。

实战建议：面试中首选 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