跳至主要內容

LeetCode 78. 子集——位运算枚举与回溯两种实现的时间对比

老张2026/4/30大约 15 分钟

LeetCode 78. 子集——位运算枚举与回溯两种实现的时间对比

适读人群：Java初中级工程师、算法进阶学习者 | 阅读时长：约20分钟 | 难度：中等

开篇故事

子集问题是我觉得最能体现"多种视角解决同一问题"的典范。这道题总共有三种本质不同的解法——位运算枚举、回溯DFS、迭代逐步扩展，每种方法背后的思维模型完全不同。

我在一次技术分享中把这三种方法同时展示出来，台下一个刚毕业的同学问：哪种方法最快？我当时回答"理论上都是 O(2^n)"，但后来想了想，这个回答太笼统了。虽然三种方法的渐进复杂度相同，但常数因子和适用场景确实有差异，特别是位运算方式在 n 较小（n <= 20）时有很大的实践优势：它没有递归开销，不需要维护 visited 状态，代码更简洁。

今天我们把这三种方法讲清楚，尤其是位运算方式——很多人知道它但不能准确说清楚为什么每个二进制位对应一个"选或不选"的决策。

一、题目解析

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

示例：

  • 输入：nums = [1,2,3]，输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
  • 输入：nums = [0]，输出：[[],[0]]

数学分析：

n 个不同元素的子集数量是 2^n（每个元素有"选"和"不选"两种状态，共 2^n 种组合）。

题目约束 n <= 10，所以 2^10 = 1024，规模很小，三种方法都绰绰有余。

三种思维模型：

  1. 位运算：用一个 n 位的二进制数，每位的 0/1 表示对应元素"不选/选"。枚举 0 到 2^n-1 的所有整数，每个整数对应一个子集。

  2. 回溯DFS：每次决定当前元素"选"还是"不选"，递归到下一个元素，直到处理完所有元素。

  3. 迭代扩展：初始只有空集，每加入一个新元素，用所有已有子集加上新元素，生成翻倍的新子集。

二、解法一：位运算枚举（最简洁，O(2^n × n)）

思路

n 个元素的每个子集，对应一个 n 位二进制数（0 到 2^n - 1）。第 j 位为 1 表示第 j 个元素被选入，为 0 表示不选。

n=3, 元素 [1,2,3]：
000 → {}（空集）
001 → {1}（第0位为1）
010 → {2}（第1位为1）
011 → {1,2}（第0和第1位为1）
100 → {3}（第2位为1）
101 → {1,3}
110 → {2,3}
111 → {1,2,3}（全集）

代码

import java.util.*;

public class Solution_BitMask {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        int total = 1 << n; // 2^n，即所有子集的数量
        List<List<Integer>> result = new ArrayList<>();
        
        // 枚举 0 到 2^n - 1 的每个整数
        for (int mask = 0; mask < total; mask++) {
            List<Integer> subset = new ArrayList<>();
            // 检查 mask 的每一位
            for (int j = 0; j < n; j++) {
                if ((mask >> j & 1) == 1) {
                    // 第 j 位为 1，选择 nums[j]
                    subset.add(nums[j]);
                }
            }
            result.add(subset);
        }
        
        return result;
    }
}

位运算关键操作解析

  • 1 << n：将 1 左移 n 位，等于 2^n。当 n=3 时，结果是 8（二进制 1000）。
  • mask >> j：将 mask 右移 j 位，使第 j 位移到最低位。
  • & 1：与 1 做按位与，取出最低位（0 或 1）。
  • 组合：(mask >> j) & 1：取出 mask 的第 j 位。

复杂度分析

  • 时间复杂度： O(2^n × n)，共 2^n 个子集，每个子集平均 n/2 个元素，生成子集需要检查 n 位。
  • 空间复杂度： O(2^n × n)，存储所有子集的空间（不算结果空间就是 O(1)）。

实践优势

  1. 无递归调用开销（函数调用有维护栈帧的成本）。
  2. 代码简洁，只有两层循环。
  3. n <= 20 时完全够用（2^20 = 1M，处理1M个子集完全没问题）。

三、解法二：回溯DFS（最通用，易扩展）

思路

每到一个位置，有两种选择：

  • 选当前元素，然后递归处理下一个位置。
  • 不选当前元素，然后递归处理下一个位置。

到达终止条件（处理完所有元素）时，将当前路径加入结果。

有别于全排列，子集问题每到一个节点就记录结果（所有中间状态都是合法子集），而不是只在叶子节点记录。

或者换一种写法：在每一层选择"从哪个下标开始取"，这样避免重复，且自动保证子集有序。

代码（两种子集写法）

写法A：每个元素选/不选

import java.util.*;

public class Solution_Backtrack_A {
    private List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0, new ArrayList<>());
        return result;
    }
    
    private void backtrack(int[] nums, int index, List<Integer> path) {
        // 每到一个节点就记录当前路径（包括空集和所有中间状态）
        result.add(new ArrayList<>(path));
        
        // 从 index 开始，依次尝试选取每个元素
        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);          // 选择 nums[i]
            backtrack(nums, i + 1, path); // 递归处理 i+1 之后的元素
            path.remove(path.size() - 1); // 回溯：撤销选择
        }
    }
}

写法B：显式"选/不选"

public class Solution_Backtrack_B {
    private List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0, new ArrayList<>());
        return result;
    }
    
    private void backtrack(int[] nums, int index, List<Integer> path) {
        if (index == nums.length) {
            // 所有元素都决定了选/不选，记录结果
            result.add(new ArrayList<>(path));
            return;
        }
        
        // 不选 nums[index]
        backtrack(nums, index + 1, path);
        
        // 选 nums[index]
        path.add(nums[index]);
        backtrack(nums, index + 1, path);
        path.remove(path.size() - 1); // 回溯
    }
}

Mermaid 图（写法A的递归树，n=3）

复杂度分析

  • 时间复杂度： O(2^n × n)，生成 2^n 个子集，每个子集复制 O(n)。
  • 空间复杂度： O(n)，递归栈深度最大为 n。

四、解法三：迭代逐步扩展（BFS风格）

思路

初始结果集为 [[]]（只含空集），每次加入一个新元素，将当前所有子集都加上这个新元素，生成新的子集，合并回结果集。

初始: result = [[]]
加入1: result = [[], [1]]        (对[]加1得[1])
加入2: result = [[], [1], [2], [1,2]]   (对[],[1]加2)
加入3: result = [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

代码

import java.util.*;

public class Solution_Iterative {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>()); // 初始：空集
        
        for (int num : nums) {
            int size = result.size();
            // 对当前所有子集，各加上 num 生成新子集
            for (int i = 0; i < size; i++) {
                List<Integer> newSubset = new ArrayList<>(result.get(i));
                newSubset.add(num);
                result.add(newSubset);
            }
        }
        
        return result;
    }
}

复杂度分析

  • 时间复杂度： O(2^n × n)，每次迭代将结果集翻倍，第 k 次迭代后有 2^k 个子集，复制每个子集需要 O(k) 时间，总时间 = sum(k × 2^k-1, k=1..n) = O(n × 2^n)。
  • 空间复杂度： O(2^n × n)，存储所有子集。比回溯方式占用更多内存（回溯是逐个生成，不需要同时存储中间结果）。

五、三种方法的实际时间对比

n子集数量 2^n位运算（理论）回溯（理论）迭代（理论）
101024约 5K ops约 5K ops约 5K ops
1532768约 500K约 500K约 500K
201M约 20M约 20M约 20M

实践中的差异（常数因子）：

  • 位运算：两层循环，无函数调用开销，Cache 友好，最快。
  • 回溯：有递归栈帧开销（函数调用、局部变量维护），但只有 O(n) 的额外空间，内存最优。
  • 迭代：同时存储所有中间子集，内存开销最大，但代码最直观。

适用场景：

  • n <= 20：三种方法均可，位运算最快。
  • n > 20 但不大：回溯更省内存（边生成边处理）。
  • 含重复元素（LeetCode 90）：只能用回溯（位运算无法直接处理去重）。

六、踩坑实录

坑一：位运算的 n 超过 31 时整型溢出

1 << n 在 n >= 31 时溢出（Java int 是 32 位，n=31 时 1 << 31 是最小负数）。

// 当 n >= 31 时危险
int total = 1 << n; // 溢出！

// 安全写法：用 long
long total = 1L << n;

不过本题 n <= 10，不会出现这个问题，但要有这个意识。

坑二：回溯写法A中，result.add 在循环开始就执行

写法A在每次进入 backtrack 时就记录 path（包括空集），这确保了所有子集（包括空集）都被记录。注意 result.add(new ArrayList<>(path)) 要在 for 循环之前，而不是在循环内部。

坑三：迭代写法中 size 必须在 for 循环外面取

// 错误：result.size() 在循环中变化，导致无限循环！
for (int i = 0; i < result.size(); i++) { 
    result.add(...); // result.size() 一直增大
}

// 正确：提前记录当前大小
int size = result.size();
for (int i = 0; i < size; i++) {
    result.add(...);
}

坑四：位运算中检查每一位的循环范围

for (int j = 0; j < n; j++) {        // 正确：检查 0 到 n-1 位
for (int j = 1; j <= n; j++) {        // 错误：多检查第n位（越界）

七、总结

子集问题三种解法的本质：

  1. 位运算：把"选/不选"编码为二进制数，枚举所有可能的编码。最快，代码最简洁，但不适合含重复元素或有额外约束的变体。
  2. 回溯：逐步构建子集，在递归树上深度优先搜索。最通用，可以轻松扩展到含重复元素（LeetCode 90）和其他约束（LeetCode 77、39 等）。
  3. 迭代扩展：直观，易理解，但内存开销大。

掌握回溯是这一系列题目的核心，因为后续的子集 II、组合、排列等都是回溯框架的变体。

解法时间复杂度空间复杂度（不含结果）可扩展性
位运算O(n × 2^n)O(1)差（难处理去重/约束）
回溯DFSO(n × 2^n)O(n)优（通用框架）
迭代扩展O(n × 2^n)O(n × 2^n)中

补充深入讲解：子集问题的数学结构与三种视角的统一

子集与幂集的数学本质

一个含 n 个不同元素的集合，它的所有子集构成的集合称为幂集（Power Set）。幂集的大小是 2^n，这个数字来自于每个元素有且只有两种状态：要么在某个子集中，要么不在。n 个元素，每个独立二选一，共 2^n 种组合。

从信息论的角度理解：描述一个特定子集需要 n 比特（每个元素对应一个比特，表示是否选入），n 比特能表示 2^n 种不同的状态，对应 2^n 个不同的子集。位掩码解法正是这个信息论观点的直接体现：用一个 n 位整数的每个比特表示对应元素是否选入。

三种方法的本质等价性

回溯法、位掩码法和迭代法看起来思路截然不同，但从数学上说它们完全等价——都枚举了所有 2^n 个子集，没有遗漏也没有重复。

回溯法是深度优先遍历一棵决策树，树的每个非叶节点有两个子节点（选或不选当前元素），叶节点对应一个完整的选择序列，即一个子集。整棵树有 2^n 个叶节点和 2^(n+1)-1 个节点，遍历所有叶节点就得到所有子集。

位掩码法是按整数从 0 到 2^n-1 的顺序枚举所有 n 位二进制串，每个二进制串对应一个子集。这相当于对上述决策树做广度优先遍历（按层从左到右），只不过我们用整数的二进制表示直接跳到每个叶节点，而不是真正地遍历树。

迭代法从空集开始，每次加入一个新元素，把所有已有子集"克隆一份，加上新元素"，得到新增的子集。这相当于逐列扩展决策树：先处理第0个元素（选或不选），再处理第1个元素……每次处理一个元素，已有子集数量翻倍。

三种方法的时间复杂度都是 O(2^n × n)：枚举 2^n 个子集，每个子集最多需要 O(n) 时间来复制到结果中。

位掩码的位运算细节

位掩码解法中，判断第 j 个元素是否在子集 mask 中，用的是 (mask >> j) & 1：先将 mask 右移 j 位，再取最低位。这个运算的意思是：把第 j 位移到最低位的位置，然后看它是 0 还是 1。

另一种等价写法是 mask & (1 << j)：1 左移 j 位，得到第 j 位为 1、其他位为 0 的掩码，与 mask 做按位与，结果非零当且仅当 mask 的第 j 位为 1。

这两种写法都常见，前者结果是 0 或 1，后者结果是 0 或 2^j。在 if 条件中两种都可以（非零为 true），但如果要用结果做数值计算，需要注意区别。

位掩码解法还有一个优势：可以通过 Integer.bitCount(mask) 直接得到子集的大小（集合中元素的数量），而不需要遍历统计。Integer.bitCount 内部使用 POPCNT 指令（在现代 CPU 上），是 O(1) 的操作，比 O(n) 的遍历快很多。这在需要过滤特定大小的子集时（比如只取大小为 k 的子集）很有用。

子集枚举的剪枝技巧

对于一些需要枚举子集的问题，不需要生成所有子集再过滤，而是在枚举过程中就进行剪枝。

一个常见的技巧是枚举某个元素的所有超集（包含该元素的所有子集）：如果 full 是全集的掩码，element 是该元素的掩码（只有对应位为1），那么枚举包含 element 的所有子集，可以用：

  • 从 mask = element 开始
  • 每次 mask = (mask + 1) | element（这样每次递增但始终包含 element 位）
  • 直到 mask > full

另一个技巧是枚举某个集合 s 的所有非空子集：

  • 从 mask = s 开始
  • 每次 mask = (mask - 1) & s（这会枚举 s 的所有子集，从 s 本身到空集之前的一步）
  • 直到 mask == 0

这些技巧在动态规划的状态压缩题（如 TSP 旅行商问题）中被大量使用，是高级位运算的重要组成部分。

子集问题的工程应用

子集枚举在工程中的应用非常广泛，最典型的是特征选择问题。在机器学习的特征工程中，当特征数量较少（n<=20）时，有时需要枚举所有特征子集，评估每个子集的模型性能，从中找到最优特征组合。这就是子集枚举的直接应用。

另一个应用是权限系统设计。在基于角色的访问控制（RBAC）中，角色是权限的子集，枚举所有可能的权限组合（即权限集合的幂集中的元素）可以用于权限审计和最小权限原则验证。

在数据库查询优化中，连接顺序优化需要枚举所有可能的表连接子集，评估不同连接顺序的代价，选择最优方案。当表的数量不超过15-20张时，位掩码子集枚举是标准的实现方式。

理解这些应用场景，有助于我们认识到子集枚举不只是算法练习，而是解决实际工程问题的基础工具。

子集生成的正确性与完整性保证

无论使用哪种方法（回溯、位掩码、迭代），都需要保证生成的子集列表满足两个性质：正确性（每个生成的子集确实是原集合的子集）和完整性（没有遗漏任何子集）。

回溯方法的正确性来自于每次选择都在合法范围内（元素下标递增，保证每个元素最多被选一次），完整性来自于对所有可能的选择进行穷举（for 循环覆盖所有未选元素）。

位掩码方法的正确性和完整性最容易验证：整数从 0 到 2^n-1 完整覆盖了所有 n 位二进制串，每个串对应唯一一个子集，既不重复也不遗漏。

迭代方法的完整性可以用数学归纳法证明：初始时 result 包含 1 个子集（空集），处理第 k 个元素后，result 包含 2^k 个子集（前 k 个元素的所有子集）。每次处理新元素时，已有的 2^(k-1) 个子集各自产生一个不包含新元素和一个包含新元素的子集，正好得到 2^k 个子集，且互不重复。

这三种方法在概念层面的互补性，使得子集问题成为学习枚举算法的最佳入口：从不同角度理解同一个问题，加深对枚举的本质认识——枚举所有可能性，一个不多、一个不少。

子集问题的边界情况

空集（[] 或 ""）是任何集合的子集，包括空集本身（空集是空集的子集）。在所有三种方法中，空集都会被正确生成：回溯在深度为 0 时记录当前路径（空路径），位掩码中整数 0 对应空集，迭代方法从空集开始。

对于 nums.length == 0 的边界情况，所有方法都应该返回包含一个空列表的列表：[[]]。这是空集的幂集，只有一个元素——空集本身。代码中通常能自动处理这种边界，但面试时要能说清楚。

子集问题的快速入门建议

初学子集问题，建议先手写 n=3 的情况（[1,2,3] 的所有8个子集），然后对照三种方法的代码逐步执行，理解每种方法是如何一步步生成这8个子集的。这种"小例子手动追踪"的学习方式，对理解回溯和枚举算法非常有效。

编辑此页
最近更新:
贡献者: xiaozhangge