wonder/leetcode-go

Fork 0

Files

T

wonder f0c7163858 vault backup: 2026-05-17 17:24:03

2026-05-17 17:24:04 +08:00

11 KiB

Raw Permalink Blame History

tags, create time

56-子集

题面

LeetCode 78. Subsets

给你一个整数数组 nums，数组中的元素 互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

思路

[!question] 💡 思考

假设 nums = [1, 2, 3]，手动枚举所有子集——你会怎么列才不会漏、不会重？

一个直观的做法是：对每个元素，问一个问题——「选它，还是不选它？」

1 选 or 不选？ → 2 选 or 不选？ → 3 选 or 不选？

每个元素恰好两个抉择，所以一共 2 × 2 × 2 = 2³ = 8 种组合，正好对应幂集大小 2^n。

[!abstract] 🎯 核心洞察

全排列的决策树是 n 叉树（每层有 n, n-1, ..., 1 个选择），而子集的决策树是一棵 完美二叉树：

决策点	选项	分支数
第 i 个元素	加入子集 / 不加入子集	2

这棵树有 n 层，叶子节点共 2^n 个——但注意：每个节点都代表一个有效子集，不只是叶子！这是子集问题与排列/组合问题的最大区别。

回溯框架三要素

子集回溯与全排列的关键差异在 「何时记录答案」：

全排列 / 组合：只有走到叶子（或指定深度）才记录
子 集 ：每个节点都是答案，边递归边记录

维护一个 path 记录当前子集，用 start 参数控制每层的遍历起点——从 start 往后选，不允许回头，天然避免重复子集。

回溯决策树（以 `nums = [1, 2, 3]` 为例）

flowchart TD
    root["[] ✅"] --> NO1["不选 1"]
    root --> YES1["选 1 → [1] ✅"]

    NO1 --> NO2["不选 2"]
    NO1 --> YES2["选 2 → [2] ✅"]

    YES1 --> NO3["不选 2 → [1] ✅"]
    YES1 --> YES3["选 2 → [1,2] ✅"]

    NO2 --> NO33["不选 3 → [] ✅"]
    NO2 --> YES33["选 3 → [3] ✅"]

    YES2 --> NO4["不选 3 → [2] ✅"]
    YES2 --> YES4["选 3 → [2,3] ✅"]

    NO3 --> NO5["不选 3 → [1] ✅"]
    NO3 --> YES5["选 3 → [1,3] ✅"]

    YES3 --> NO6["不选 3 → [1,2] ✅"]
    YES3 --> YES6["选 3 → [1,2,3] ✅"]

    classDef leaf fill:#FFD700,stroke:#DAA520,color:#000;
    class NO33,YES33,NO4,YES4,NO5,YES5,NO6,YES6 leaf;

关键观察：

共 2^(n+1) - 1 个节点（n 层满二叉树的总结点数），每到一个节点就将 path 拷贝入结果
用 start 保证不回头：右子树永远不选当前及之前的元素

方法一：回溯（标准模板）⭐ 推荐

[!tip] 🔑 写法要点

var result [][]int

var dfs func(start int)
dfs = func(start int) {
    // ⚠️ 每个节点都收集答案（区别于排列只在叶子记录）
    result = append(result, append([]int(nil), path...))

    for i := start; i < len(nums); i++ {
        path = append(path, nums[i])  // 做选择
        dfs(i + 1)                     // 递归：下一个位置从 i+1 开始
        path = path[:len(path)-1]      // 撤销选择
    }
}

dfs(0)

为什么从 i+1 开始而不是像全排列那样从头遍历？

子集不允许回头 → [1, 2] 和 [2, 1] 算同一个子集
固定顺序（从前向后选）即可天然去重，无需 used[] 数组
这等价于从 n 个元素中选出 k 个的组合思想
时间复杂度：O(n × 2^n) —— 2^n 个子集，每个拷贝 O(n)
空间复杂度：O(n) —— 递归栈深度

方法二：迭代（逐元素扩展法）

[!tip] 🔑 核心思想

从空集出发，每遇到一个新元素，把已有的所有子集各自加上该元素作为新子集追加到结果中。

初始:       [[]]
遇到 1:     [[] , [1]]           ← 已有子集 + 每个加 1
遇到 2:     [[] , [1], [2], [1,2]]  ← 上一步全部 + 每个加 2
遇到 3:     ...                  ← 同上规律

每次迭代子集数量翻倍：1 → 2 → 4 → 8 → ... → 2^n。

时间复杂度：O(n × 2^n)
空间复杂度：O(1) 额外（不计返回值）

方法三：位运算（枚举掩码）

[!note] 🔑 核心思想

n 个元素的幂集大小为 2^n，可以用 0 到 2^n - 1 的二进制数编码：

第 j 位为 1 → 包含 nums[j]
第 j 位为 0 → 不包含 nums[j]

nums = [1, 2, 3]

000 → []
001 → [1]
010 → [2]
011 → [1,2]
100 → [3]
101 → [1,3]
110 → [2,3]
111 → [1,2,3]

优点：代码极简，仅两层 for 循环
缺点：无法提前终止（回溯可以通过剪枝跳过无效分支），面试时通常作为加分项展示多样性。

时间复杂度：O(n × 2^n)
空间复杂度：O(n)

代码提示

[!abstract] 📝 回溯通用骨架（子集版）

var result [][]int
var path []int

var dfs func(start int)
dfs = func(start int) {
    // ① Base case 隐式处理——每到一个节点就记录
    result = append(result, append([]int(nil), path...))

    // ② 从 start 往后枚举，不允许回头
    for i := start; i < len(nums); i++ {
        path = append(path, nums[i])  // 做选择
        dfs(i + 1)                     // 递归
        path = path[:len(path)-1]      // 撤销选择
    }
}

dfs(0)
return result

[!summary] 📋 子集 vs 排列 vs 组合

问题	决策树	何时记录	遍历方式	去重手段
子集 (LC 78)	二叉树	每个节点	`for i := start`	`start` 防回头
全排列 (LC 46)	n 叉树	叶子节点	`for i := range` + `used[]`	`used[]` 标记
组合 (LC 77)	二叉树	指定深度	`for i := start`	`start` 防回头

共同口诀：

做选择 → 递归探索 → 撤销选择

子集的特殊之处：

排列和组合只收集「完整方案」；子集收集「每一个中间状态」。

代码

[!success] ✅ 方法一：回溯（⭐ 推荐）

// subsets 返回 nums 的所有子集（幂集）。
//
// 时间复杂度：O(n * 2^n) — 共 2^n 个子集，每个拷贝 O(n)
// 空间复杂度：O(n) — 递归栈深度为 n
func subsets(nums []int) [][]int {
	var result [][]int
	path := make([]int, 0, len(nums))

	var dfs func(start int)
	dfs = func(start int) {
		// 每个节点都是答案，直接记录
		result = append(result, append([]int(nil), path...))

		for i := start; i < len(nums); i++ {
			path = append(path, nums[i]) // 做选择
			dfs(i + 1)                   // 递归：下一层从 i+1 开始
			path = path[:len(path)-1]    // 撤销选择
		}
	}

	dfs(0)
	return result
}

[!success] ✅ 方法二：迭代（逐元素扩展）

// subsetsIterative 使用迭代法求所有子集。
//
// 时间复杂度：O(n * 2^n)
// 空间复杂度：O(1) 额外（不计返回值）
func subsetsIterative(nums []int) [][]int {
	result := [][]int{{}}

	for _, num := range nums {
		n := len(result)
		for i := 0; i < n; i++ {
			newSubset := append(result[i], num)
			result = append(result, append([]int(nil), newSubset...))
		}
	}

	return result
}

[!success] ✅ 方法三：位运算

// subsetsBitManipulation 通过位枚举求所有子集。
//
// 时间复杂度：O(n * 2^n)
// 空间复杂度：O(n)
func subsetsBitManipulation(nums []int) [][]int {
	n := len(nums)
	result := make([][]int, 0, 1<<n) // 预分配容量

	for mask := 0; mask < (1<<n); mask++ {
		subset := make([]int, 0)
		for j := 0; j < n; j++ {
			if mask&(1<<j) != 0 { // 检查第 j 位是否为 1
				subset = append(subset, nums[j])
			}
		}
		result = append(result, subset)
	}

	return result
}

[!success] ✅ 单元测试

import (
	"slices"
	"testing"
)

func TestSubsets(t *testing.T) {
	tests := []struct {
		name   string
		input  []int
		expect [][]int
	}{
		{name: "示例1", input: []int{1, 2, 3}, expect: [][]int{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}},
		{name: "单元素", input: []int{0}, expect: [][]int{{},{0}}},
	}

	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			got := subsets(append([]int{}, tt.input...))
			slices.SortFunc(got, func(a, b []int) int {
				if len(a) != len(b) {
					return len(a) - len(b)
				}
				return slices.Compare(a, b)
			})
			slices.SortFunc(tt.expect, func(a, b []int) int {
				if len(a) != len(b) {
					return len(a) - len(b)
				}
				return slices.Compare(a, b)
			})
			if !slices.Equal(got, tt.expect) {
				t.Errorf("subsets(%v) = %v; want %v", tt.input, got, tt.expect)
			}
		})
	}
}

技巧

[!danger] ⚠️ Go 切片陷阱：存引用还是存值？

与全排列一样，path 指向同一底层数组。如果不创建独立副本直接存入 result，后续回溯修改会污染已记录的结果。

// ❌ 危险：存的是引用，后续 path 变化会影响所有已记录的子集
result = append(result, path)

// ✅ 正确：创建独立副本
result = append(result, append([]int(nil), path...))

[!tip] 🔑 何时用位运算？

当 n ≤ 20 且需要简洁实现时，位运算是最短的代码路径。但在面试中建议优先写回溯——它展现了你对算法范式的理解，且更容易扩展到变体问题（如含重复元素的情况）。

[!quote] 💬 延伸思考

幂集的大小是指数级 2^n。这意味着：

任何子集算法都不可能低于 O(2^n) —— 你必须至少列出所有子集
n > 20 时暴力枚举就会超时，必须借助数学性质（如排序后的贪心、前缀和优化等）
这也解释了为什么 LeetCode 将本题约束为 n ≤ 10 —— 留出了大量练习空间

总结

[!summary] 📋 本章要点回顾

子集问题是回溯的入门基石：

模型最简——二叉决策树，每步只需回答「选 or 不选」

记录时机特殊——每个节点都是合法子集，而非仅叶子

三种实现等价——回溯、迭代扩展、位枚举，各有适用场景

可迁移到大量变体：含重复元素回溯/57-子集 II、分割回文串、电话号码组合

口诀：一进一出两改两回，选了加，回去退，每个节点都要收。

[!example] 🔀 关联变体题

回溯/55-全排列 — 回溯入门第一题，n 叉树 vs 二叉树
LeetCode 90. Subsets II — 含重复元素的子集（需排序 + 同层去重）
LeetCode 77. Combinations — 从 n 中选 k 个（固定深度的子集）
LeetCode 216. Combination Sum III — 组合之和 III（加和条件过滤）
LeetCode 40. Combination Sum II — 组合总和 II（含重复元素 + 目标和）
回溯/57-电话号码的字母组合 — 笛卡尔积型回溯，每层候选集不同

11 KiB Raw Permalink Blame History Unescape Escape