针对 LeetCode 78 子集问题，提供 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] <= 10nums 中的所有元素 互不相同子集问题是组合数学中的基础问题：给定一个包含 n 个不同元素的集合，求其所有子集（包括空集和全集）。对于 n 个元素，共有 2ⁿ 个子集。
本题的关键点：
[1,2] 和 [2,1] 视为同一子集（但题目输出为列表，通常按原序）由于 n ≤ 10，最大子集数为 2¹⁰ = 1024，属于可枚举范围，适合使用位运算或回溯法。
💡 幂集（Power Set）：一个集合 S 的所有子集构成的集合，记作 P(S) 或 2^S。
每个元素有两种状态：在子集中（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，即可生成所有子集。
total = 1 << n（即 2ⁿ）mask = 0 到 total - 1mask，检查其二进制位：
nums[i] 加入当前子集对每个元素，做出选或不选的决策，递归构建所有可能的子集。
cur = 0 开始cur == n，将当前路径加入结果nums[cur]，递归处理 cur + 1nums[cur]，递归处理 cur + 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;
}
}
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 测试。回溯法更直观，位运算法更简洁。
(mask & (1 << i)) != 01 << i：将 1 左移 i 位，得到只有第 i 位为 1 的数mask & (1 << i)：按位与，若结果非 0，说明 mask 的第 i 位为 1nums = [1,2,3], mask = 5 (101)1<<0=1 (001), 101 & 001 = 001 ≠ 0 → 选 nums[0]=11<<1=2 (010), 101 & 010 = 000 = 0 → 不选 nums[1]=21<<2=4 (100), 101 & 100 = 100 ≠ 0 → 选 nums[2]=3[1,3]以 nums = [1,2,3] 为例：
[]
/ \
[1] []
/ \ / \
[1,2] [1] [2] []
/ \ / \ / \ / \
[1,2,3][1,2][1,3][1][2,3][2][3][]
result.add(new ArrayList<>(path));
path 对象path 的状态（空列表）| 特性 | 位运算法 | 回溯法 |
|---|---|---|
| 时间复杂度 | O(n × 2ⁿ) | O(n × 2ⁿ) |
| 空间复杂度 | O(n) | O(n) |
| 代码长度 | 短 | 较长 |
| 可读性 | 中（需理解位运算） | 高（逻辑清晰） |
| 输出顺序 | 按 mask 顺序 | 按 DFS 顺序 |
| 扩展性 | 难（如加约束） | 易（可加剪枝） |
📌 面试推荐回溯法：更易解释，且是解决复杂子集问题（如含重复、带约束）的基础。
⚠️ 这是理论下限，因为必须输出所有子集，且每个子集平均长度为 n/2。
subset：O(n)path：O(n)📌 标准答案的空间复杂度为 O(n)（仅考虑算法运行所需额外空间）。
mask 从 0 开始？答：mask = 0 对应二进制全 0，即空集，是子集的一部分。
答：可以。但会影响输出顺序：
答：需在回溯时跳过重复选择：
nums 排序Set 去重（效率低）// 关键代码（在回溯法基础上）
if (index > 0 && nums[index] == nums[index - 1] && !used[index - 1]) {
continue; // 跳过重复
}
答：可以，但效率低：
[[]]nums[i] 生成新子集预计算 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)，实际收益微乎其微。
有人尝试直接 result.add(path)，但会导致：
List 对象path）正确做法：必须深拷贝。
已知结果数量为 2ⁿ，可预先设置容量：
List<List<Integer>> result = new ArrayList<>(1 << n);
避免动态扩容的内存拷贝开销。
使用栈模拟递归：
// 伪代码
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);
}
}
但代码复杂，面试不推荐。
| 操作 | 含义 | 示例 |
|---|---|---|
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 |
模板：
void backtrack(路径，选择列表){
if (满足结束条件){
result.add(路径);
return;
}
for (选择 : 选择列表){
做选择;
backtrack(路径，新选择列表);
撤销选择;
}
}
| 问题类型 | 是否有序 | 是否可重复 | 典型题号 |
|---|---|---|---|
| 子集 | 否 | 否 | LeetCode 78 |
| 组合 | 否 | 否 | LeetCode 77 |
| 全排列 | 是 | 否 | LeetCode 46 |
| 子集 II | 否 | 是 | LeetCode 90 |
| 组合总和 | 否 | 是 | LeetCode 39 |
💡 子集 = 所有可能的组合（包括空集和全集）
答：（写出回溯法代码后解释）
答：
答：不能。
2³⁰ ≈ 10⁹，内存和时间均不可接受答：两种方法：
size() 排序// 方法 2：分层回溯
for (int size = 0; size <= n; size++) {
generateSubsetsOfSize(nums, 0, new ArrayList<>(), size, result);
}
答：因为回溯是共享状态的递归。
path 仍包含该元素💡 虽然实际中很少直接生成所有子集（因 2ⁿ 增长太快），但子集思想广泛应用于各种组合优化问题。
| 题号 | 题目 | 难度 | 关联点 |
|---|---|---|---|
| 90 | 子集 II | 中等 | 含重复元素，需去重 |
| 77 | 组合 | 中等 | 回溯生成固定大小子集 |
| 39 | 组合总和 | 中等 | 可重复选择 + 目标和 |
| 40 | 组合总和 II | 中等 | 不可重复 + 去重 |
| 46 | 全排列 | 中等 | 回溯生成排列 |
| 47 | 全排列 II | 中等 | 含重复元素的排列 |
| 22 | 括号生成 | 中等 | 有效括号的回溯 |
| 51 | N 皇后 | 困难 | 经典回溯问题 |
| 784 | 字母大小写全排列 | 中等 | 位运算/回溯应用 |
| 1286 | 字母组合迭代器 | 中等 | 按需生成子集 |
学习路径建议：掌握本题（无重复子集）→ 90（去重技巧）→ 77（固定大小子集）→ 39/40（带目标和的组合）→ 46（排列问题）
结语：子集问题虽看似简单，却是理解组合生成和回溯思想的绝佳入口。掌握它，不仅能解决这一道题，更能为后续更复杂的组合优化问题打下坚实基础。希望本文能助你在算法之路上走得更远！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online