Java版LeetCode热题100之子集：从位运算到回溯的全面解析

Java版LeetCode热题100之子集：从位运算到回溯的全面解析

摘要：本文将深入剖析 LeetCode 热题 100 中的经典组合问题——子集（Subsets）。我们将从题目出发，系统讲解两种主流解法：位运算法（迭代） 和 回溯法（递归），并提供完整可运行的 Java 实现。文章涵盖时间/空间复杂度分析、常见面试问题、实际应用场景、相关题目推荐等模块，帮助读者不仅掌握解题技巧，更能理解其背后的算法思想与工程价值。

一、原题回顾

题目名称：子集
题目编号：LeetCode 78
难度等级：中等

题目描述

给你一个整数数组 nums，数组中的元素 互不相同。返回该数组所有可能的子集（幂集）。

• 解集不能包含重复的子集
• 你可以按任意顺序返回解集

示例

示例 1： 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2： 输入：nums = [0] 输出：[[],[0]] 

提示

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

二、原题分析

子集问题是组合数学中的基础问题：给定一个包含 n 个不同元素的集合，求其所有子集（包括空集和全集）。对于 n 个元素，共有 2ⁿ 个子集。

本题的关键点：

• 元素无重复 → 无需去重处理
• 子集无序 → [1,2] 和 [2,1] 视为同一子集（但题目输出为列表，通常按原序）
• 输出顺序任意 → 无需排序

由于 n ≤ 10，最大子集数为 2¹⁰ = 1024，属于可枚举范围，适合使用位运算或回溯法。

💡 幂集（Power Set）：一个集合 S 的所有子集构成的集合，记作 P(S) 或 2^S。

三、答案构思

3.1 方法一：位运算法（迭代）

核心思想

每个元素有两种状态：在子集中（1）或不在子集中（0）。因此，n 个元素的子集可对应一个 n 位的二进制数（mask）。

例如，nums = [1,2,3]：

• mask = 0 (000) → []
• mask = 1 (001) → [3]
• mask = 2 (010) → [2]
• mask = 3 (011) → [2,3]
• …
• mask = 7 (111) → [1,2,3]

通过枚举 mask 从 0 到 2ⁿ - 1，即可生成所有子集。

算法步骤

1. 计算总子集数：total = 1 << n（即 2ⁿ）
2. 遍历 mask = 0 到 total - 1
3. 对每个 mask，检查其二进制位：
   • 若第 i 位为 1，则将 nums[i] 加入当前子集
4. 将当前子集加入结果集

3.2 方法二：回溯法（递归）

核心思想

对每个元素，做出选或不选的决策，递归构建所有可能的子集。

• 路径（Path）：当前已选择的元素
• 选择列表：剩余未决策的元素
• 结束条件：所有元素均已决策

算法步骤

1. 从索引 cur = 0 开始
2. 若 cur == n，将当前路径加入结果
3. 否则：
   • 选择nums[cur]，递归处理 cur + 1
   • 撤销选择（回溯）
   • 不选择nums[cur]，递归处理 cur + 1

🔑 回溯法天然保证子集按原数组顺序生成，且无重复。

四、完整答案（Java 实现）

4.1 方法一：位运算法（迭代）

classSolution{publicList<List<Integer>>subsets(int[] nums){List<List<Integer>> result =newArrayList<>();int n = nums.length;int total =1<< n;// 2^n// 枚举所有 mask: 0 ~ 2^n - 1for(int mask =0; mask < total; mask++){List<Integer> subset =newArrayList<>();// 检查 mask 的每一位for(int i =0; i < n; i++){// 若第 i 位为 1，则包含 nums[i]if((mask &(1<< i))!=0){ subset.add(nums[i]);}} result.add(subset);}return result;}}

4.2 方法二：回溯法（递归）

classSolution{publicList<List<Integer>>subsets(int[] nums){List<List<Integer>> result =newArrayList<>();List<Integer> path =newArrayList<>();backtrack(nums,0, path, result);return result;}privatevoidbacktrack(int[] nums,int index,List<Integer> path,List<List<Integer>> result){// 结束条件：所有元素已决策if(index == nums.length){ result.add(newArrayList<>(path));// 深拷贝return;}// 选择当前元素 path.add(nums[index]);backtrack(nums, index +1, path, result); path.remove(path.size()-1);// 撤销选择// 不选择当前元素backtrack(nums, index +1, path, result);}}

✅ 两种方法均可通过 LeetCode 测试。回溯法更直观，位运算法更简洁。

五、代码分析

5.1 位运算法详解

关键操作：(mask & (1 << i)) != 0

• 1 << i：将 1 左移 i 位，得到只有第 i 位为 1 的数
• mask & (1 << i)：按位与，若结果非 0，说明 mask 的第 i 位为 1

示例：nums = [1,2,3], mask = 5 (101)

• i=0: 1<<0=1 (001), 101 & 001 = 001 ≠ 0 → 选 nums[0]=1
• i=1: 1<<1=2 (010), 101 & 010 = 000 = 0 → 不选 nums[1]=2
• i=2: 1<<2=4 (100), 101 & 100 = 100 ≠ 0 → 选 nums[2]=3
• 结果：[1,3]

5.2 回溯法详解

递归树结构

以 nums = [1,2,3] 为例：

 [] / \ [1] [] / \ / \ [1,2] [1] [2] [] / \ / \ / \ / \ [1,2,3][1,2][1,3][1][2,3][2][3][] 

• 左分支：选择当前元素
• 右分支：不选择当前元素
• 叶节点：所有子集（共 8 个）

深拷贝的重要性

result.add(newArrayList<>(path));

• 必须创建副本，否则所有子集将指向同一个 path 对象
• 最终结果会全部等于最后一次 path 的状态（空列表）

5.3 两种方法对比

📌 面试推荐回溯法：更易解释，且是解决复杂子集问题（如含重复、带约束）的基础。

六、时间复杂度与空间复杂度分析

6.1 时间复杂度：O(n × 2ⁿ)

• 子集总数：2ⁿ
• 每个子集的构建成本：O(n)（需遍历所有元素判断是否包含）
• 总时间：2ⁿ × n = O(n × 2ⁿ)

⚠️ 这是理论下限，因为必须输出所有子集，且每个子集平均长度为 n/2。

6.2 空间复杂度：O(n)

• 位运算法：
  • 临时列表 subset：O(n)
  • 无递归栈
• 回溯法：
  • 递归栈深度：O(n)
  • 临时路径 path：O(n)
• 结果集空间：O(n × 2ⁿ)，但通常不计入空间复杂度（题目要求输出）

📌 标准答案的空间复杂度为 O(n)（仅考虑算法运行所需额外空间）。

七、常见问题解答（FAQ）

Q1: 为什么位运算法中 mask 从 0 开始？

答：mask = 0 对应二进制全 0，即空集，是子集的一部分。

Q2: 回溯法中“选择”和“不选择”的顺序能交换吗？

答：可以。但会影响输出顺序：

• 先“不选择” → 子集按元素缺失顺序生成
• 先“选择” → 子集按元素存在顺序生成
• 题目允许任意顺序，故无影响

Q3: 如何处理含重复元素的子集（LeetCode 90）？

答：需在回溯时跳过重复选择：

1. 先对 nums 排序
2. 在“不选择”分支后，跳过所有相同元素
3. 或使用 Set 去重（效率低）

// 关键代码（在回溯法基础上）if(index >0&& nums[index]== nums[index -1]&&!used[index -1]){continue;// 跳过重复}

Q4: 能否用 BFS 实现？

答：可以，但效率低：

• 初始队列：[[]]
• 每次取出一个子集，分别添加 nums[i] 生成新子集
• 需记录已处理元素，避免重复
• 空间复杂度更高（需存储中间状态）

八、优化思路

8.1 位运算法优化：减少位运算

预计算 1 << i 的值：

int[] masks =newint[n];for(int i =0; i < n; i++){ masks[i]=1<< i;}// 使用 masks[i] 代替 (1 << i)

但现代 JVM 会优化 (1 << i)，实际收益微乎其微。

8.2 回溯法优化：避免深拷贝（不可行）

有人尝试直接 result.add(path)，但会导致：

• 所有子集引用同一个 List 对象
• 最终结果全为空（因回溯会清空 path）

正确做法：必须深拷贝。

8.3 预分配结果集大小

已知结果数量为 2ⁿ，可预先设置容量：

List<List<Integer>> result =newArrayList<>(1<< n);

避免动态扩容的内存拷贝开销。

8.4 迭代式回溯（消除递归）

使用栈模拟递归：

// 伪代码Stack<State> stack =newStack<>(); stack.push(initialState);while(!stack.isEmpty()){State state = stack.pop();if(state.isComplete()){ add toresult;}else{// 生成“选择”和“不选择”两个新状态 stack.push(notChooseState); stack.push(chooseState);}}

但代码复杂，面试不推荐。

九、数据结构与算法基础知识点回顾

9.1 什么是子集（Subset）？

• 定义：若集合 A 的所有元素都在集合 B 中，则 A 是 B 的子集
• 幂集：一个集合的所有子集构成的集合
• 性质：
  • 空集是任何集合的子集
  • 任何集合是自身的子集
  • n 元集合的子集数为 2ⁿ

9.2 位运算基础

9.3 回溯算法核心

• 三要素：
  1. 路径：已做出的选择
  2. 选择列表：当前可做的选择
  3. 结束条件：到达决策树的叶子

模板：

voidbacktrack(路径, 选择列表){if(满足结束条件){ result.add(路径);return;}for(选择 : 选择列表){ 做选择;backtrack(路径, 新选择列表); 撤销选择;}}

9.4 子集 vs 组合 vs 排列

💡 子集 = 所有可能的组合（包括空集和全集）

十、面试官提问环节（模拟）

Q1: 请手写子集，并解释两种方法的区别。

答：（写出回溯法代码后解释）

• 位运算法：利用二进制 mask 枚举所有可能，代码简洁但需位运算知识
• 回溯法：对每个元素做“选/不选”决策，逻辑清晰，易于扩展
• 两者时间复杂度相同，但回溯法更适合处理带约束的问题

Q2: 时间复杂度为什么是 O(n × 2ⁿ)？能否优化？

答：

• 共有 2ⁿ 个子集，每个子集平均长度 n/2 → 总操作数 ≈ n × 2ⁿ
• 无法优化时间复杂度，因为必须输出所有子集
• 但可优化常数因子（如预分配空间）

Q3: 如果数组很大（如 n=30），还能用这两种方法吗？

答：不能。

• 2³⁰ ≈ 10⁹，内存和时间均不可接受
• 此时应：
  • 使用生成器模式按需生成子集
  • 或问题本身有特殊约束可剪枝（如只求大小为 k 的子集）

Q4: 如何按子集大小排序输出？

答：两种方法：

1. 后处理：生成所有子集后，按 size() 排序
2. 修改回溯：按子集大小分层生成（先生成大小 0，再 1，…）

// 方法2：分层回溯for(int size =0; size <= n; size++){generateSubsetsOfSize(nums,0,newArrayList<>(), size, result);}

Q5: 回溯中的“撤销选择”为什么重要？

答：因为回溯是共享状态的递归。

• 若不撤销，后续分支会基于错误的状态计算
• 例如：第一次选择后未移除，第二次“不选择”分支的 path 仍包含该元素
• 导致结果重复或错误

十一、这道算法题在实际开发中的应用

11.1 权限管理系统

• 用户权限是角色的子集
• 枚举所有可能的权限组合，用于测试或配置

11.2 特征工程（机器学习）

• 从 n 个特征中选择子集，训练不同模型
• 用于特征选择（Feature Selection）

11.3 配置组合测试

• 软件有多个配置项（如 A/B/C 开关）
• 枚举所有配置组合，进行兼容性测试

11.4 背包问题变种

• 0-1 背包：每个物品选或不选
• 子集枚举是暴力解法的基础

11.5 电路设计

• 逻辑门的输入组合
• 枚举所有输入子集，验证电路行为

💡 虽然实际中很少直接生成所有子集（因 2ⁿ 增长太快），但子集思想广泛应用于各种组合优化问题。

十二、相关题目推荐

学习路径建议：掌握本题（无重复子集）→ 90（去重技巧）→ 77（固定大小子集）→ 39/40（带目标和的组合）→ 46（排列问题）

十三、总结与延伸

13.1 核心收获

• 子集问题的标准解法是位运算或回溯
• 位运算法简洁，回溯法通用
• 时间复杂度 O(n × 2ⁿ) 是理论下限
• 回溯的核心是“状态恢复”

13.2 延伸思考

如何生成第 k 个子集？

• 利用 k 的二进制表示直接构造
• 无需生成前面的子集
• 时间复杂度 O(n)

子集和问题（Subset Sum）？

• 给定目标和，判断是否存在子集和等于目标
• 是 NP-Complete 问题
• 可用动态规划（DP）优化

并行子集生成？

• 对高位 mask 并行（如前两位决定 4 个大组）
• 但 n 较小时 overhead 大，不实用

13.3 学习建议

1. 动手实现：手写两种方法，理解其差异
2. 掌握回溯模板：适用于大多数组合问题
3. 理解位运算：在状态压缩 DP 中广泛应用
4. 刷相关题：巩固子集、组合、排列的解题套路
5. 思考扩展：如含重复、带约束、按需生成等

结语：子集问题虽看似简单，却是理解组合生成和回溯思想的绝佳入口。掌握它，不仅能解决这一道题，更能为后续更复杂的组合优化问题打下坚实基础。希望本文能助你在算法之路上走得更远！