生成所有子集
对每个元素选择取用或跳过
生成所有子集 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
为什么要生成子集
许多竞赛题要求您尝试一个小集合的每个子集。借助递归，您可以清晰且可靠地列出所有子集。🧩
选择或跳过每个元素
核心思路是：对每个元素做一次二元选择：将其加入，或将其跳过。每组完整的选择都会得到一个子集。
有多少个子集
包含 n 个元素的集合恰好有 2 的 n 次方个子集，因为每个元素都会使数量翻倍。因此请让 n 保持较小，约为 20 或更少。
递归方案
沿着数组移动一个索引。在每个索引处进行两次分支：一次选取该元素，另一次跳过它。
基例
当索引越过最后一个元素时，当前路径就是一个完整的子集。这就是用于记录它的基例。
代码中的子集递归
这个递归遍历会在末尾记录一个子集，然后从每个索引开始探索跳过和选取两种情况。
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])通过撤销操作进行回溯
执行 append 添加一个元素后，在递归返回时将其移除，这样下一个分支就能从干净的状态开始。这个撤销步骤正是回溯的核心。
cur.append(a[i])
gen(i + 1, cur)
cur.pop()位掩码替代方案
您也可以将从 0 到 2 的 n 次方减 1 的每个整数映射到一个子集，其中每个位标记一个已包含的元素。
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]存储前先复制
请始终存储当前列表的副本，而不是列表本身。否则后续更改会覆盖您保存的每个子集。⚠️
生成 combinations
要获取固定大小 k 的子集，请在选中的数量达到 k 后停止该分支。这样就能将子集生成转为 combinations。
子集的应用场景
子集枚举可以解决小规模的背包问题、组队选择和可行性检查，在这些问题中您必须测试每种可能的选择。
快速检查
包含 n 个元素的集合有多少个子集？
回顾：为每个元素创建分支
您学会了通过选择或跳过每个元素来列出所有 subsets，并在每个分支后撤销操作。由于数量为 2 的 n 次方，请让 n 保持较小。🎯
常见问题解答
「生成所有子集」课时是免费的吗？
是的 — 「生成所有子集」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「生成所有子集」这节课中我会学到什么？
对每个元素选择取用或跳过 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「生成所有子集」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。