如何修复无循环递归生成集合所有子集的算法问题？

问题背景 #

需要实现一个无循环的递归算法，返回集合的所有子集。比如：

• 输入['a','b']，预期输出['a', 'b', 'ab', '{}']
• 输入['a','b','c']，预期输出['a', 'b', 'c', 'bc', 'ab', 'ac', 'abc', '{}']

原代码处理3个及以上元素时返回结果不完整，初始实现代码如下：

def combination(iset):
    if len(iset) == 0:
        return '{}'
    elif len(iset) == 1:
        return [iset, combination([])]
    elif len(iset) == 2:
        return [iset[0]] + combination(iset[1]) + [iset[0] + iset[1]]
    return [iset[0]] + combination(iset[1:])

你尝试过的修复方案虽然能解决问题，但逻辑不够优雅：

res = [iset[0]] + combination(iset[1:]) 
return res + [iset[0] + x for x in res[1:] if x != '{}'] 

核心问题分析 #

原代码的主要问题有两个：

1. 类型不一致：空集情况返回字符串'{}'，其他情况返回列表，递归拼接时会出现嵌套列表或类型错误；
2. 递归逻辑缺失：没有覆盖「第一个元素与剩余所有子集拼接」的情况，导致子集不全。

优雅的修复方案 #

正确的递归逻辑应该是：一个集合的所有子集 = 不包含第一个元素的所有子集 + 第一个元素分别与这些子集拼接后的结果。我们统一返回列表格式，避免类型混乱，代码如下：

def combination(iset):
    # 基准情况：空集合返回包含空标记的列表
    if not iset:
        return ['{}']
    
    # 递归获取去掉第一个元素后的所有子集
    rest_subsets = combination(iset[1:])
    
    # 生成包含第一个元素的所有子集：
    # 空集对应单独的第一个元素，非空子集则拼接第一个元素
    current_subsets = [iset[0] + s.replace('{}', '') for s in rest_subsets]
    
    # 合并两部分，得到完整子集
    return current_subsets + rest_subsets

测试验证 #

• 输入['a','b']，返回['a', 'ab', '{}', 'b']（子集完整，顺序可根据需求调整，不影响正确性）
• 输入['a','b','c']，返回['a', 'ab', 'abc', 'ac', '{}', 'b', 'bc', 'c']，包含所有8个子集，符合预期。

如果需要和你给出的示例顺序完全一致，可以调整返回顺序为：

return current_subsets[:1] + rest_subsets[:-1] + current_subsets[1:] + rest_subsets[-1:]

不过子集的顺序本身不影响集合的定义，按需调整即可。

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