408 lines
11 KiB
Markdown
408 lines
11 KiB
Markdown
---
|
||
tags: ["LeetCode", "回溯", "数组", "位运算", "中等"]
|
||
create time: 2026-05-17 10:30
|
||
---
|
||
|
||
# 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]` 为例）
|
||
|
||
```mermaid
|
||
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] 🔑 写法要点
|
||
|
||
```go
|
||
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] 📝 回溯通用骨架（子集版）
|
||
|
||
```go
|
||
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] ✅ 方法一：回溯（⭐ 推荐）
|
||
|
||
```go
|
||
// 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] ✅ 方法二：迭代（逐元素扩展）
|
||
|
||
```go
|
||
// 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] ✅ 方法三：位运算
|
||
|
||
```go
|
||
// 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] ✅ 单元测试
|
||
|
||
```go
|
||
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`，后续回溯修改会污染已记录的结果。
|
||
|
||
```go
|
||
// ❌ 危险：存的是引用，后续 path 变化会影响所有已记录的子集
|
||
result = append(result, path)
|
||
|
||
// ✅ 正确：创建独立副本
|
||
result = append(result, append([]int(nil), path...))
|
||
```
|
||
|
||
> [!tip] 🔑 何时用位运算？
|
||
|
||
当 `n ≤ 20` 且需要简洁实现时，位运算是最短的代码路径。但在面试中建议优先写回溯——它展现了你对算法范式的理解，且更容易扩展到变体问题（如含重复元素的情况）。
|
||
|
||
> [!quote] 💬 延伸思考
|
||
|
||
幂集的大小是指数级 `2^n`。这意味着：
|
||
|
||
1. **任何子集算法都不可能低于 O(2^n)** —— 你必须至少列出所有子集
|
||
2. `n > 20` 时暴力枚举就会超时，必须借助数学性质（如排序后的贪心、前缀和优化等）
|
||
3. 这也解释了为什么 LeetCode 将本题约束为 `n ≤ 10` —— 留出了大量练习空间
|
||
|
||
---
|
||
|
||
## 总结
|
||
|
||
> [!summary] 📋 本章要点回顾
|
||
|
||
> 子集问题是回溯的入门基石：
|
||
>
|
||
> 1. **模型最简**——二叉决策树，每步只需回答「选 or 不选」
|
||
> 2. **记录时机特殊**——每个节点都是合法子集，而非仅叶子
|
||
> 3. **三种实现等价**——回溯、迭代扩展、位枚举，各有适用场景
|
||
> 4. **可迁移到大量变体**：含重复元素 [[回溯/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-电话号码的字母组合]]** — 笛卡尔积型回溯，每层候选集不同
|