如何用单个Python函数高效生成和为n的正整数递增组合

架构老林

2026-8-2

生成和为n的正整数递增组合的高效实现

需求

编写一个接收正整数n（n>0）的函数，返回所有和为n的正整数递增组合。

原实现及问题

尝试用单个函数结合itertools.combinations_with_replacement实现，代码如下：

def all_combinations_sum_to_n(n):
    from itertools import combinations_with_replacement

    combinations_list = []

    if n < 1:
        return combinations_list

    l = [i for i in range(1, n + 1)]
    for i in range(1, n + 1):
        combinations_list = combinations_list + (list(combinations_with_replacement(l, i)))

    result = [list(i) for i in combinations_list if sum(i) == n]
    result.sort()
    return result

但当传入n=20时，因时空复杂度过高（推测为O(n*n!)）被系统终止进程。