Python递归生成列表所有子序列存储为嵌套列表问题求解

原代码错误原因 #

你的代码存在两个核心问题：

1. 递归终止返回逻辑错误：当遍历到列表末尾（ind == n）时，需要将当前临时路径ans作为独立子序列返回，而非直接返回ans本身。同时Python列表是可变引用类型，必须复制后再返回，否则后续pop操作会修改已存入的列表内容。
2. 结果拼接逻辑不匹配：你每次递归返回的是当前层级下所有子序列组成的嵌套列表，原代码的终止返回值和拼接动作不匹配，导致结果要么扁平化要么多层嵌套。

extend和append结果异常的原因 #

• 用extend时，终止条件直接返回ans（如[1,3]），extend会将该列表的元素逐个拆分加入结果，最终得到没有嵌套的一维列表，也不会包含空子序列。
• 用append时，每次下层递归返回的是包含多个子序列的列表，append会将整个返回列表当作单个元素加入，最终得到多层嵌套的错误结构。

修正后代码 #

基础正确版本 #

def printSubsequences(ind, ans, l, n):
    final_ans = []
    if ind == n:
        # 终止时返回当前路径的副本，作为单个子序列放在列表中
        return [ans.copy()]
    # 选当前元素的分支
    ans.append(l[ind])
    final_ans.extend(printSubsequences(ind+1, ans, l, n))
    # 回溯，不选当前元素的分支
    ans.pop()
    final_ans.extend(printSubsequences(ind+1, ans, l, n))
    return final_ans

# 测试调用
result = printSubsequences(0, [], [1,3,2], 3)
print(result)

运行输出：[[1, 3, 2], [1, 3], [1, 2], [1], [3, 2], [3], [2], []]

匹配示例顺序的版本 #

如果需要和你给出的输出顺序（按子序列长度升序排列）完全一致，可以对结果加排序：

result = sorted(printSubsequences(0, [], [1,3,2], 3), key=lambda x: len(x))
print(result)

运行输出：[[], [1], [3], [2], [1, 3], [1, 2], [3, 2], [1, 3, 2]]，完全符合预期。

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