如何实现有序集合幂集的深度优先枚举？

需求说明 #

给定有序集合[1,2,3,...]，对其幂集进行枚举时需遵循以下规则：

• 所有包含1的子集必须排在不含1的子集之前；
• 在不含1的子集中，所有包含2的子集必须排在不含2的子集之前；
• 以此类推，对后续每个元素都保持该优先级。

例如集合[1,2,3,4]的枚举顺序为：

()
(1,)
(1, 2)
(1, 2, 3)
(1, 2, 3, 4)
(1, 2, 4)
(1, 3)
(1, 3, 4)
(1, 4)
(2,)
(2, 3)
(2, 3, 4)
(2, 4)
(3,)
(3, 4)
(4,)

递归实现思路 #

核心采用回溯+递归的方式，无需跟踪已访问子集，逻辑如下：

1. 维护一个当前路径（记录当前子集的元素）和一个起始索引（控制从哪个元素开始处理，避免重复生成子集）；
2. 初始时先输出空集，然后从第一个元素开始遍历；
3. 对每个元素：
   • 将其加入当前路径，输出该子集；
   • 递归处理该元素的下一个索引，带着更新后的路径；
   • 回溯：将该元素从路径中移除，继续处理下一个元素。

这种方式天然满足题目要求的优先级：先处理包含当前元素的所有子集（递归深入），再处理不含当前元素的后续子集。

Python 代码实现 #

def power_set_dfs(nums):
    def backtrack(start, path):
        # 输出当前路径对应的子集
        print(tuple(path))
        # 从start开始遍历，避免重复生成子集
        for i in range(start, len(nums)):
            # 选择当前元素
            path.append(nums[i])
            # 递归处理下一个元素
            backtrack(i + 1, path)
            # 回溯，移除当前元素
            path.pop()
    
    backtrack(0, [])

# 测试示例
power_set_dfs([1,2,3,4])

运行这段代码，就能得到题目要求的枚举顺序。

内容的提问来源于stack exchange，提问作者kc9jud