子集（位运算解法）
📌 定义
给定一个不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[],
[1],
[2],
[1,2],
[3],
[1,3],
[2,3],
[1,2,3]
]
核心思路
使用**位掩码（Bitmask）**枚举所有子集：
- n 个元素有 2^n 个子集
- 用 n 位二进制数表示每个子集
- 第 i 位为 1 表示包含第 i 个元素
示例: nums = [1, 2, 3]
共有 2^3 = 8 个子集
掩码 | 二进制 | 子集
-----|-------|------
0 | 000 | []
1 | 001 | [1]
2 | 010 | [2]
3 | 011 | [1,2]
4 | 100 | [3]
5 | 101 | [1,3]
6 | 110 | [2,3]
7 | 111 | [1,2,3]
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 位运算 | O(n × 2^n) | O(1) | 枚举所有掩码 |
| 回溯法 | O(n × 2^n) | O(n) | 递归栈空间 |
| 迭代法 | O(n × 2^n) | O(1) | 动态添加 |
Go 代码
Go 实现
package main
import "fmt"
// 方法1: 位运算
func subsets(nums []int) [][]int {
n := len(nums)
result := make([][]int, 0, 1<<n)
// 枚举所有子集
for mask := 0; mask < (1 << n); mask++ {
subset := make([]int, 0)
// 检查每一位
for i := 0; i < n; i++ {
if mask&(1<<i) != 0 {
subset = append(subset, nums[i])
}
}
result = append(result, subset)
}
return result
}
// 方法2: 使用位计数优化
func subsetsOptimized(nums []int) [][]int {
n := len(nums)
result := make([][]int, 0, 1<<n)
for mask := 0; mask < (1 << n); mask++ {
// 预分配空间（popcount）
subset := make([]int, 0, popcount(mask))
for i := 0; i < n; i++ {
if mask&(1<<i) != 0 {
subset = append(subset, nums[i])
}
}
result = append(result, subset)
}
return result
}
// 统计1的个数
func popcount(n int) int {
count := 0
for n > 0 {
n &= n - 1
count++
}
return count
}
func main() {
nums := []int{1, 2, 3}
result := subsets(nums)
fmt.Println("所有子集:")
for _, subset := range result {
fmt.Println(subset)
}
}思路展开
位掩码枚举详解
nums = [1, 2, 3]
n = 3, 共 2^3 = 8 个子集
mask=0 (000):
第0位=0，不包含nums[0]
第1位=0，不包含nums[1]
第2位=0，不包含nums[2]
子集: []
mask=1 (001):
第0位=1，包含nums[0]=1
第1位=0
第2位=0
子集: [1]
mask=2 (010):
第0位=0
第1位=1，包含nums[1]=2
第2位=0
子集: [2]
mask=3 (011):
第0位=1，包含nums[0]=1
第1位=1，包含nums[1]=2
第2位=0
子集: [1,2]
mask=4 (100):
第0位=0
第1位=0
第2位=1，包含nums[2]=3
子集: [3]
mask=5 (101):
第0位=1，包含nums[0]=1
第1位=0
第2位=1，包含nums[2]=3
子集: [1,3]
mask=6 (110):
第0位=0
第1位=1，包含nums[1]=2
第2位=1，包含nums[2]=3
子集: [2,3]
mask=7 (111):
第0位=1，包含nums[0]=1
第1位=1，包含nums[1]=2
第2位=1，包含nums[2]=3
子集: [1,2,3]
位运算操作详解
检查第i位是否为1:
mask & (1 << i)
示例: mask=5 (101), 检查第1位
5 & (1 << 1) = 101 & 010 = 000 = 0 (第1位是0)
示例: mask=5 (101), 检查第0位
5 & (1 << 0) = 101 & 001 = 001 ≠ 0 (第0位是1)
示例: mask=5 (101), 检查第2位
5 & (1 << 2) = 101 & 100 = 100 ≠ 0 (第2位是1)
为什么是 2^n 个子集？
数学证明:
每个元素有2种选择：选或不选
1个元素: 2^1 = 2个子集
[], [1]
2个元素: 2^2 = 4个子集
[], [1], [2], [1,2]
3个元素: 2^3 = 8个子集
[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]
通用公式: C(n,0) + C(n,1) + ... + C(n,n) = 2^n
经典题目
LeetCode 问题
- 子集 - LeetCode 78
- 子集 II - LeetCode 90（包含重复元素）
- 子集问题（回溯解法）
扩展问题
- 生成所有k个元素的子集
- 子集和等于目标值
⚖️ 优缺点
优点
- ✅ 实现简单：一个循环遍历所有掩码
- ✅ 空间高效：O(1) 额外空间
- ✅ 无需递归：避免栈溢出
- ✅ 顺序明确：按掩码值有序生成
缺点
- ❌ 仅适用于小规模：n > 20 时 2^n 太大
- ❌ 无法剪枝：必须枚举所有 2^n 个
- ❌ 重复元素处理复杂：需要额外去重
🎨 应用场景
💡 优化技巧
相关主题
- 子集问题（回溯解法） - 回溯算法解法
- 组合问题 - 选k个元素
- 位运算 - 返回位运算总览
- 背包问题 - 子集和问题