如何使用迭代法按指定顺序生成数组的所有子集

排序规则拆解 #

你要求的子集排序逻辑可总结为：

1. 空集排在最前
2. 剩余子集优先按最小元素升序排列
3. 最小元素相同的子集按长度从小到大排列
4. 长度相同的子集按元素字典序升序排列

常规二进制遍历方案是按子集对应二进制数的大小排序，不符合上述规则，可采用「固定最小前缀+按长度扩展」的迭代思路实现。 #

实现步骤 #

• 初始化结果列表，先加入空集
• 遍历数组每个下标i，枚举所有**最小元素恰好为nums[i]**的子集，避免与前面生成的子集重复
• 对每个下标i，先生成仅包含nums[i]的单元素子集作为当前层级的初始值
• 按子集长度从小到大扩展：每次取当前长度的子集，往末尾添加位置在子集最后一个元素之后的元素，生成长度+1的新子集，直到无法扩展为止
• 将当前i对应的所有子集按顺序加入总结果列表

代码示例（Python） #

def generate_ordered_subsets(nums):
    # 先排序保证数组升序，符合字典序要求
    nums = sorted(nums)
    n = len(nums)
    res = [[]]  # 第一个元素为空集
    
    for i in range(n):
        # 存储所有最小元素为nums[i]的子集
        current_level = [[nums[i]]]
        ptr = 0
        # 按长度从小到大迭代扩展
        while ptr < len(current_level):
            cur_sub = current_level[ptr]
            # 获取当前子集最后一个元素的下标
            last_pos = nums.index(cur_sub[-1])
            # 往后拼接新元素，生成长度+1的子集
            for j in range(last_pos + 1, n):
                new_sub = cur_sub.copy()
                new_sub.append(nums[j])
                current_level.append(new_sub)
            ptr += 1
        # 将当前层级的子集加入总结果
        res.extend(current_level)
    return res

效果验证 #

输入[1,2,3,4]调用函数，输出结果为：
[[], [1], [1, 2], [1, 3], [1, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [1, 2, 3, 4], [2], [2, 3], [2, 4], [2, 3, 4], [3], [3, 4], [4]]
完全匹配要求的排序规则。

补充说明：如果输入数组存在重复元素，可将子集存储内容改为元素对应的下标，最后再映射为实际值，避免index方法匹配错误。

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