如何按输入元素出现顺序递归生成非空子集 附Python参考代码

实现思路 #

你当前的回溯代码是通过标记每个位置选或不选生成子集，生成顺序不符合要求且包含空集，我们可以按子集长度从小到大，同长度下按原数组元素出现顺序生成组合的逻辑实现，刚好匹配输出要求。

方案1：使用内置itertools.combinations实现（最简写法） #

itertools.combinations默认按原数组的索引升序生成固定长度的组合，完全符合顺序要求：

from itertools import combinations

# 读取输入
numbers = list(map(int, input().split()))
# 遍历所有非空子集的长度
for sub_len in range(1, len(numbers) + 1):
    # 生成当前长度的所有组合
    for comb in combinations(numbers, sub_len):
        # 拼接为字符串输出
        print(''.join(map(str, comb)))

方案2：手写回溯实现（不依赖第三方库） #

通过控制元素选择的起始位置避免重复组合，按子集长度分组存储后按序输出：

numbers = list(map(int, input().split()))
n = len(numbers)
# 按子集长度分组存储结果，索引对应子集长度
result = [[] for _ in range(n + 1)]

def backtrack(start_idx, current_path):
    path_len = len(current_path)
    # 非空路径存入对应长度的分组
    if path_len > 0:
        result[path_len].append(''.join(map(str, current_path)))
    # 仅从起始位置往后选择元素，避免生成重复组合
    for i in range(start_idx, n):
        current_path.append(numbers[i])
        backtrack(i + 1, current_path)
        current_path.pop()

backtrack(0, [])
# 按长度从小到大输出所有结果
for sub_len in range(1, n + 1):
    for item in result[sub_len]:
        print(item)

两种方案运行输入5 3 8都可以得到你给出的样例输出。

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