集合算法：高效生成幂集的两种技术实现

幂集是一个给定集合的所有子集构成的集合，包含空集和集合本身。若原集合有 N 个元素，则幂集大小为 2^N。

在算法面试中，不重复、不遗漏地生成所有子集，是评估结构化思维和递归建模能力的基础题。

方法一：二进制位掩码

每个元素在子集中只有两种状态：出现或不出现。这正好对应二进制中的 1 和 0。

实现逻辑

• 集合大小为 N，子集总数为 1 << N。
• 使用从 0 到 2^N - 1 的整数作为子集编码。
• 对每个编码，检查第 j 位是否为 1。
• 如果第 j 位为 1，就把原集合中下标为 j 的元素加入当前子集。

这种方法结构紧凑，不需要递归，适合元素数量较少的场景。

方法二：回溯生成

回溯法把问题建模为一棵决策树。每一层递归都决定一个元素是否进入当前子集。

• 分支一：选择当前元素，然后继续处理下一个元素。
• 分支二：不选择当前元素，直接继续处理下一个元素。
• 当递归深度等于集合长度时，将当前路径复制到结果集中。

回溯法更容易扩展到包含剪枝、去重或约束条件的子集问题。