LeetCode 子集问题：Java 位运算与回溯法解析

LeetCode 子集问题：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 方法一：位运算法（迭代）

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        int total = 1 << n; // 2^n

        // 枚举所有 mask: 0 ~ 2^n - 1
        for (int mask = 0; mask < total; mask++) {
            List<Integer> subset = new ArrayList<>();
            // 检查 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 方法二：回溯法（递归）

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtrack(nums, 0, path, result);
        return result;
    }

    private void backtrack(int[] nums, int index, List<Integer> path, List<List<Integer>> result) {
        // 结束条件：所有元素已决策
        if (index == nums.length) {
            result.add(new ArrayList<>(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(new ArrayList<>(path));

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

5.3 两种方法对比

特性	位运算法	回溯法
时间复杂度	O(n × 2ⁿ)	O(n × 2ⁿ)
空间复杂度	O(n)	O(n)
代码长度	短	较长
可读性	中（需理解位运算）	高（逻辑清晰）
输出顺序	按 mask 顺序	按 DFS 顺序
扩展性	难（如加约束）	易（可加剪枝）

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

---

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

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 = new int[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 = new ArrayList<>(1 << n);

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

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

使用栈模拟递归：

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

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

---

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

9.1 什么是子集（Subset）？

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

9.2 位运算基础

操作	含义	示例
1 << n	2ⁿ	1 << 3 = 8
mask & (1 << i)	检查第 i 位是否为 1	5 & 4 = 4 ≠ 0
`mask	(1 << i)`	设置第 i 位为 1
mask ^ (1 << i)	翻转第 i 位	5 ^ 4 = 1

9.3 回溯算法核心

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

模板：

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

9.4 子集 vs 组合 vs 排列

问题类型	是否有序	是否可重复	典型题号
子集	否	否	LeetCode 78
组合	否	否	LeetCode 77
全排列	是	否	LeetCode 46
子集 II	否	是	LeetCode 90
组合总和	否	是	LeetCode 39

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

---

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

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, new ArrayList<>(), size, result);
}

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

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

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

---

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

11.1 权限管理系统

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

11.2 特征工程（机器学习）

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

11.3 配置组合测试

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

11.4 背包问题变种

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

11.5 电路设计

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

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

---

十二、相关题目推荐

题号	题目	难度	关联点
90	子集 II	中等	含重复元素，需去重
77	组合	中等	回溯生成固定大小子集
39	组合总和	中等	可重复选择 + 目标和
40	组合总和 II	中等	不可重复 + 去重
46	全排列	中等	回溯生成排列
47	全排列 II	中等	含重复元素的排列
22	括号生成	中等	有效括号的回溯
51	N 皇后	困难	经典回溯问题
784	字母大小写全排列	中等	位运算/回溯应用
1286	字母组合迭代器	中等	按需生成子集

学习路径建议：掌握本题（无重复子集）→ 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. 思考扩展：如含重复、带约束、按需生成等

---

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