子集问题（Subsets）
📌 定义
给定一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。可以按任意顺序返回解集。
示例:
输入: nums = [1,2,3]
输出:
[
[],
[1],
[2],
[1,2],
[3],
[1,3],
[2,3],
[1,2,3]
]
输入: nums = [0]
输出: [[],[0]]
核心思路
与组合问题的区别：
- 组合：只收集叶子节点（固定长度）
- 子集：收集所有节点（所有长度）
决策树示例 [1,2,3]:
[] ← 收集
/ | \
[1] [2] [3] ← 收集
/ \ |
[1,2][1,3] [2,3] ← 收集
|
[1,2,3] ← 收集
每个节点都是一个有效的子集
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 回溯法 | O(n × 2^n) | O(n) | 2^n个子集 |
| 位运算 | O(n × 2^n) | O(1) | 枚举所有掩码 |
| 迭代法 | O(n × 2^n) | O(1) | 动态添加 |
Go 代码
Go 实现
package main
import "fmt"
// 方法1: 回溯法
func subsets(nums []int) [][]int {
result := [][]int{}
path := []int{}
var backtrack func(start int)
backtrack = func(start int) {
// 收集当前路径
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
// 从start开始遍历
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
backtrack(i + 1)
path = path[:len(path)-1]
}
}
backtrack(0)
return result
}
// 方法2: 位运算
func subsetsBitmask(nums []int) [][]int {
n := len(nums)
result := [][]int{}
for mask := 0; mask < (1 << n); mask++ {
subset := []int{}
for i := 0; i < n; i++ {
if mask&(1<<i) != 0 {
subset = append(subset, nums[i])
}
}
result = append(result, subset)
}
return result
}
func main() {
nums := []int{1, 2, 3}
result := subsets(nums)
fmt.Println("所有子集:")
for _, subset := range result {
fmt.Println(subset)
}
}思路展开
回溯过程详解
nums = [1, 2, 3]
backtrack(0, []):
收集 []
i=0: path=[1]
backtrack(1, [1]):
收集 [1]
i=1: path=[1,2]
backtrack(2, [1,2]):
收集 [1,2]
i=2: path=[1,2,3]
backtrack(3, [1,2,3]):
收集 [1,2,3]
返回
回溯: path=[1,2]
返回
回溯: path=[1]
i=2: path=[1,3]
backtrack(3, [1,3]):
收集 [1,3]
返回
回溯: path=[1]
返回
回溯: path=[]
i=1: path=[2]
...
结果: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]
迭代法过程详解
nums = [1, 2, 3]
初始: result = [[]]
处理1:
现有子集: [[]]
添加1后: [[1]]
result = [[], [1]]
处理2:
现有子集: [[], [1]]
添加2后: [[2], [1,2]]
result = [[], [1], [2], [1,2]]
处理3:
现有子集: [[], [1], [2], [1,2]]
添加3后: [[3], [1,3], [2,3], [1,2,3]]
result = [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
去重策略详解
nums = [1, 2, 2]
排序后: [1, 2, 2]
树形结构:
[]
/ | \
[1] [2] [2]×
/ \ / \
[1,2][1,2] [2,2] [2,2]×
| | |
[1,2,2][1,2,2]×[2,2,2]×
× 标记的是被剪枝的分支
去重条件:
if i > start and nums[i] == nums[i-1]:
continue
在同一层（i > start）且与前一个元素相同时跳过
经典题目
LeetCode 问题
扩展问题
- 大小为k的所有子集
- 和为target的所有子集
⚖️ 优缺点
优点
- ✅ 简单直观：每个节点都收集
- ✅ 易于扩展：容易添加约束条件
- ✅ 三种方法：可根据场景选择
缺点
- ❌ 指数复杂度：2
- ❌ 大规模问题：n > 20时性能差
🎨 应用场景
💡 优化技巧
💡 子集 vs 组合 vs 排列
| 特性 | 子集 | 组合 | 排列 |
|---|---|---|---|
| 长度 | 任意 | 固定 | 固定 |
| 顺序 | 不考虑 | 不考虑 | 考虑 |
| 数量 | 2^n | C(n,k) | n! |
| 收集 | 所有节点 | 叶子节点 | 叶子节点 |
| 例子 | [], [1], [1,2] | [1,2], [1,3] | [1,2], [2,1] |