【LeetCode 热题 100】78. 子集——（解法三）位运算

Problem: 78. 子集
题目：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

整体思路

这段代码同样旨在解决 “子集 (Subsets)” 问题。与前面基于回溯/DFS的递归解法不同，此版本采用了一种完全不同的、基于 位掩码（Bitmask） 的迭代方法。这种方法非常巧妙，它将“生成子集”的问题与“二进制数的表示”完美地对应起来。

算法的核心思想是：

1. 子集与二进制数的映射关系

   • 一个包含 n 个元素的集合，其所有子集的数量是 2^n。
   • 巧合的是，从 0 到 2^n - 1，也正好有 2^n 个不同的整数。
   • 我们可以将这 n 个元素与一个 n 位的二进制数的每一位进行一一对应。例如，nums = [a, b, c]，n=3。我们可以用一个 3 位的二进制数来表示一个子集：
     • 第 0 位对应元素 a
     • 第 1 位对应元素 b
     • 第 2 位对应元素 c
   • 规则：如果二进制数的某一位是 1，则表示对应的元素被选中加入子集；如果是 0，则表示不选。
   • 示例：
     • 二进制 000 (十进制 0) -> {} (空集)
     • 二进制 001 (十进制 1) -> {a}
     • 二进制 010 (十进制 2) -> {b}
     • 二进制 101 (十进制 5) -> {a, c}
     • 二进制 111 (十进制 7) -> {a, b, c}
   • 这样，从 0 到 2^n - 1 的每一个整数，都唯一地对应着一个子集。

2. 算法实现步骤：

   • 外层循环：算法的主体是一个 for 循环，它从 i = 0 遍历到 (1 << n) - 1。这里的 (1 << n) 就是 2^n。这个循环变量 i 就充当了位掩码，它的二进制表示决定了当前要生成哪个子集。
   • 内层循环与位运算：
     • 对于每一个位掩码 i，算法进入一个内层循环，从 j = 0 到 n-1，检查 i 的每一位。
     • 检查第 j 位：通过位运算 (i >> j & 1) == 1 来检查 i 的第 j 位是否为 1。
       • i >> j: 将 i 右移 j 位，使得原来的第 j 位移动到最右边（第 0 位）。
       • & 1: 将右移后的结果与 1 进行按位与操作。如果原来的第 j 位是 1，结果就是 1；如果是 0，结果就是 0。
     • 构建子集：如果检查结果为 1，说明 nums[j] 这个元素应该被包含在当前子集中，于是将其加入到临时的 subset 列表中。
   • 收集结果：内层循环结束后，subset 列表就构建完毕了，将其加入到最终的结果列表 ans 中。

通过这种方式，算法以一种确定性的、非递归的方式，系统地生成了所有 2^n 个子集。

完整代码

class Solution {
    /**
     * 计算给定数组的所有子集（幂集）。
     * (位掩码迭代法)
     * @param nums 不含重复元素的整数数组
     * @return 包含所有子集的列表
     */
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        // 预先设定ArrayList的容量为 2^n，可以提高性能，避免多次内部扩容。
        // (1 << n) 是 2^n 的高效写法。
        List<List<Integer>> ans = new ArrayList<>(1 << n);
        
        // 步骤 1: 外层循环遍历所有可能的子集，用整数 0 到 2^n - 1 作为位掩码。
        for (int i = 0; i < (1 << n); i++) {
            // 为每个位掩码创建一个新的子集列表。
            List<Integer> subset = new ArrayList<>();
            
            // 步骤 2: 内层循环检查位掩码 i 的每一位，以确定哪些元素应加入子集。
            for (int j = 0; j < n; j++) {
                // 关键的位运算：检查 i 的第 j 位是否为 1。
                // (i >> j) 将 i 的第 j 位移到最右边。
                // (& 1)   检查最右边一位是否为 1。
                if ((i >> j & 1) == 1) {
                    // 如果第 j 位为 1，则将 nums[j] 加入到当前子集中。
                    subset.add(nums[j]);
                }
            }
            // 将构建好的子集加入到最终结果列表中。
            ans.add(subset);
        }
        return ans;
    }
}

时空复杂度

时间复杂度：O(N * 2^N)

1. 外层循环：for (int i = 0; i < (1 << n); i++) 执行 2^N 次。
2. 内层循环：for (int j = 0; j < n; j++) 执行 N 次。
3. 循环内部操作：位运算和 subset.add() 都是 O(1) 的操作。

综合分析：
算法的总操作次数是外层循环次数乘以内层循环次数，即 2^N * N。
因此，总的时间复杂度为 O(N * 2^N)。这与回溯法的时间复杂度量级是相同的，因为问题的内在计算量就是这么多。

空间复杂度：O(N) (不考虑输出数组)

1. 主要存储开销：我们分析的是额外辅助空间。
   • List<Integer> subset: 在每次外层循环中，都会创建一个临时的 subset 列表。在任意时刻，只有一个 subset 列表存在于内存中。这个列表的最大长度为 N（当位掩码为 11...1 时）。因此，这部分空间是 O(N)。
   • 其他变量 n, i, j 都是常数空间。

综合分析：
如果不考虑存储最终结果的 ans 列表（其空间为 O(N * 2^N)），算法所需的额外辅助空间主要由临时的 subset 列表决定。因此，其空间复杂度为 O(N)。

参考灵神