
本文详解如何用位运算法正确生成数组的所有子集(即幂集),修复原代码中子集构建逻辑错误,提供完整可运行示例及关键注意事项。
本文详解如何用位运算法正确生成数组的所有子集(即幂集),修复原代码中子集构建逻辑错误,提供完整可运行示例及关键注意事项。
在 JavaScript 中生成一个数组的所有子集(也称“幂集”)是一个经典算法问题。核心思想是:长度为 n 的数组共有 2ⁿ 个子集,每个子集可唯一对应一个 n 位二进制数——第 j 位为 1 表示包含原数组第 j 个元素,为 0 则不包含。
原代码的主要问题在于:内层循环中每次匹配到一位为 1 就单独 push([arr[j]]),导致结果不是子集数组,而是所有被选中元素的单元素数组拼接而成的扁平列表。例如输入 [1,2,3] 会输出 [[1],[2],[1],[3],[2],[3]],完全丢失子集结构。
✅ 正确做法是:
- 外层遍历
0到2ⁿ − 1(共2ⁿ个掩码); - 对每个掩码
i,初始化一个空子集subset = []; - 内层遍历每一位
j,若(i >> j) & 1为真,则将arr[j]加入当前subset; - 循环结束后,将完整构建的
subset推入结果数组subsets。
以下是修复后的完整实现:
使用 Husky 将 pre-commit、pre-push 和 commit-msg 检查集成到仓库中,以便代理和开发人员在更改离开工作站之前运行相同的本地防护措施。
立即学习“Java免费学习笔记(深入)”;
const getAllSubsets = arr => {
const n = arr.length;
const subsets = [];
// 遍历所有可能的掩码:0 到 2^n - 1
for (let i = 0; i < (1 << n); i++) {
const subset = [];
// 检查掩码 i 的每一位
for (let j = 0; j < n; j++) {
// 若第 j 位为 1,则包含 arr[j]
if ((i >> j) & 1) {
subset.push(arr[j]);
}
}
subsets.push(subset);
}
return subsets;
};
// 测试
console.log(getAllSubsets([1, 2, 3]));
// 输出:[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]? 关键说明与注意事项:
- 使用
i >> j & 1比(1 更直观(检查第 <code>j位是否置位),语义等价但可读性更强; - 子集顺序按二进制升序排列(空集 → 单元素 → 双元素 → …),符合数学幂集定义;
- 时间复杂度为
O(n × 2ⁿ),空间复杂度为O(2ⁿ × n)(存储全部子集),对大数组需谨慎使用; - 若需去重子集(如原数组含重复元素),应先排序 + 跳过重复掩码,或改用回溯法配合剪枝。
该方法简洁高效,是理解位运算与组合枚举的优质实践案例。

















