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<>();intn=nums.length;inttotal=1<<n;// 2^n// 枚举所有 mask: 0 ~ 2^n - 1for(intmask=0;mask<total;mask++){List<Integer>subset=newArrayList<>();// 检查 mask 的每一位for(inti=0;i<n;i++){// 若第 i 位为 1，则包含 nums[i]if((mask&(1<<i))!=0){subset.add(nums[i]);}}result.add(subset);}returnresult;}}

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

classSolution{publicList<List<Integer>>subsets(int[]nums){List<List<Integer>>result=newArrayList<>();List<Integer>path=newArrayList<>();backtrack(nums,0,path,result);returnresult;}privatevoidbacktrack(int[]nums,intindex,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(inti=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()){Statestate=stack.pop();if(state.isComplete()){addtoresult;}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(intsize=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ⁿ 增长太快），但子集思想广泛应用于各种组合优化问题。

十二、相关题目推荐

学习路径建议：

1. 掌握本题（无重复子集）
2. → 90（去重技巧）
3. → 77（固定大小子集）
4. → 39/40（带目标和的组合）
5. → 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. 思考扩展：如含重复、带约束、按需生成等

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