子集枚举

递归与回溯

说明

每个元素分别选择或跳过；共有 2ⁿ 个子集。

分析

n 位掩码的第 i 位决定是否选择第 i 个元素，从 0 到 2ⁿ−1 遍历即可覆盖全部子集。实现紧凑，但结果数量指数增长。

图解推演

以 [1,2] 为例，低位控制 1、高位控制 2。四个掩码与四个子集一一对应，因此不会遗漏；这里按下标区分元素，输入重复值会产生数值相同的子集。输出每个子集仍需扫描 n 位，总工作为 O(n·2ⁿ)。

查看图表代码

适用前提与边界

位移宽度受整数位数限制；很大的 n 应使用递归或迭代扩展且避免一次保存所有结果。

示例输入与调用

fmt.Println(Subsets([]int{1, 2}))

运行输出

[[] [1] [2] [1 2]]

完整 Go 示例

package main

import "fmt"

func Subsets(a []int) [][]int {
	out := [][]int{}
	for mask := 0; mask < 1<<len(a); mask++ {
		part := []int{}
		for i, x := range a {
			if mask>>i&1 == 1 {
				part = append(part, x)
			}
		}
		out = append(out, part)
	}
	return out
}

func main() {
	fmt.Println(Subsets([]int{1, 2}))
}