使用位掩码枚举子集
通过整数遍历所有子集
使用位掩码枚举子集 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
将子集表示为数字
每个包含 n 个元素的子集都可以映射到一个整数。从 0 开始计数，每个数字的位恰好标记出其中包含哪些元素。🙂
有多少个子集
一个包含 n 个元素的集合有 2^n 个子集。因此，让一个整数从 0 循环到 2^n 减 1，就能恰好访问每个子集一次。
for mask in range(1 << n):
pass # mask is one subset1 << n 表示数量
移位操作 1 << n 等于 2 的 n 次方。这是表示子集循环上限的简洁而快速的方式。
读取第 i 位
要判断元素 i 是否属于子集，请使用掩码和左移 i 位的 1 检查它的位。结果非零就表示它已被包含。
if mask & (1 << i):
take(items[i])构建所选列表
遍历每个位的位置，收集对应位已设置的元素。这样就能将一个掩码转换为它所表示的具体子集。
chosen = [items[i] for i in range(n) if mask & (1 << i)]空集与全集
掩码 0 表示空子集，全 1 掩码表示全集。由于循环会覆盖每个值，这两种情况都无需额外处理。
对子集求和
在循环内，将所选元素相加，为每个子集计算得分。这是许多小型暴力枚举解法的核心。
total = sum(v[i] for i in range(n) if mask & (1 << i))统计置位位数
所选元素的数量等于掩码的置位计数。在 Python 中，bin(mask).count('1') 可以立即得到这个数量。
size = bin(mask).count("1")注意上限
由于共有 2^n 个子集，这种方法只适用于较小的 n。当 n 约等于 20 时，通常就是完整枚举的实际上限。
位掩码为何更优
一个整数循环就能替代繁琐的嵌套循环，而且位运算速度很快。代码简短、清晰，也易于测试。
可复用的模式
遍历掩码，解码其中的位，为子集计算得分，并记录最佳结果。记住这个模板后，许多子集问题都会变得很常规。
快速检查
您想要检查掩码所编码的子集中是否包含元素 i。
回顾
让掩码从 0 循环到 2^n 减 1，使用掩码和左移的 1 读取各个位，并为每个子集计算得分。这是适用于较小 n 的简洁暴力枚举方法。🚀
常见问题解答
「使用位掩码枚举子集」课时是免费的吗？
是的 — 「使用位掩码枚举子集」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「使用位掩码枚举子集」这节课中我会学到什么？
通过整数遍历所有子集 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「使用位掩码枚举子集」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 暴力搜索也是有效策略
- 使用 itertools 枚举
- 使用位掩码枚举子集
- 巧妙缩小搜索空间