子集枚举如何用位掩码实现？为什么一个整数能表示一个集合？

简化版

子集枚举可以用一个整数 mask 表示选择状态：第 i 位为 1 表示选中 nums[i]，为 0 表示不选。长度为 n 的数组一共有 2^n 个子集，所以枚举 mask 从 0 到 (1<<n)-1 即可。

详细版

位掩码的本质是把多个布尔选择压进一个整数。对每个 mask，遍历每一位 i，用 (mask & (1 << i)) != 0 判断第 i 个元素是否在当前子集中。mask=0 表示空集，mask=(1<<n)-1 表示全集。

这种写法适合 n 不太大的场景，时间复杂度是 O(n * 2^n)，空间复杂度取决于输出规模。面试中重点是能解释“位和元素下标的一一映射”，以及不要让 1 << n 在大 n 时溢出。

完整版教学

一、为什么一个整数能表示一个集合

一个集合里每个元素只有两种状态：选或不选。这正好对应二进制位的 1 和 0。数组长度为 n 时，我们可以用第 i 位表示 nums[i] 是否被选中。

nums = [a, b, c]
mask = 101（二进制）
       ^ ^ ^
       c b a
表示选择 a 和 c

这就是位掩码状态压缩：把多个布尔变量压到一个整数里。

二、为什么一共有 2^n 个 mask

每个元素有 2 种选择，n 个元素互相独立，所以总状态数是：

2 * 2 * ... * 2 = 2^n

n=3 时，mask 从 000 到 111，刚好 8 个状态。

mask	子集
`000`	`[]`
`001`	`[a]`
`010`	`[b]`
`111`	`[a,b,c]`

记忆钩子：子集就是每个元素选/不选，二进制天然就是选/不选。

三、如何判断某一位是否被选中

判断第 i 位是否为 1，使用：

(mask & (1 << i)) != 0

1 << i 会构造一个只有第 i 位为 1 的数。与 mask 做按位与后，如果结果不为 0，就说明这一位被选中。

mask     = 1010
1 << 1   = 0010
& result = 0010  => 第 1 位被选中

下标从 0 开始，所以第 0 位对应第一个元素。

四、代码模板

List<List<Integer>> subsets(int[] nums) {
    int n = nums.length;
    List<List<Integer>> ans = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> cur = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                cur.add(nums[i]);
            }
        }
        ans.add(cur);
    }
    return ans;
}

这段代码把所有状态都枚举出来，所以输出规模本身就是 2^n。

五、和回溯枚举有什么区别

回溯是递归地做“选/不选”，位掩码是用整数直接表示每一种选法。两者本质相同，只是表达方式不同。

写法	优点	适合场景
回溯	易扩展剪枝	需要约束、去重、路径控制
位掩码	代码短、状态可存储	`n` 小、需要枚举所有状态

如果题目还要按字典序、处理重复元素，回溯往往更灵活；如果只是枚举所有子集，位掩码很爽快。

六、边界和溢出要注意

1 << n 使用的是 int，当 n >= 31 时可能溢出。面试里子集枚举通常 n 很小，比如 n <= 20，否则 2^n 输出也不可承受。

n=20 => 约 1,048,576 个状态
n=30 => 约 1,073,741,824 个状态

如果确实需要更大位数，可以用 long 的 1L << n，但输出所有子集仍然会爆炸。

七、常见误区与追问

误区：把第 1 位当成第一个元素。 编程里通常第 0 位对应下标 0。
误区：循环写成 mask <= (1 << n)。 最后一个合法 mask 是 (1<<n)-1，小于即可。
误区：忽略 1 << n 溢出。 大 n 要用 1L 或重新评估算法可行性。
追问：空集如何表示？ mask=0，所有位都是 0。
追问：全集如何表示？ mask=(1<<n)-1，低 n 位全为 1。
追问：和回溯复杂度一样吗？ 都要枚举 2^n 个子集，只是实现方式不同。

八、加强记忆

子集位掩码的主线是“位 = 元素开关”。第 i 位为 1 就选 nums[i]，为 0 就不选；所有子集就是从 0 枚举到 2^n-1。会写 (mask & (1<<i)) != 0，再记住空集、全集和溢出边界，这类题基本就稳了。

简化版

详细版