如何查找和为给定值的严格递减正整数组合并优化低效实现代码

• 时间复杂度过高：原代码采用暴力枚举所有组合的思路，从1~N-1中选取任意K个元素的组合总数为2^(N-1)，属于指数级复杂度。N=50时组合总量超过500万亿，自然需要数小时才能跑完；N=200时不可能在可接受时间内执行完成，所谓的结果错误基本都是代码未执行完毕导致的误判。
• 无效遍历过多：K个严格递减正整数的最小和为1+2+…+K = K*(K+1)/2，当这个值大于N时不可能存在符合要求的组合，原代码将K遍历到N，做了大量无用计算。

你需要实现的功能本质是计算将N拆分为若干互不相同正整数的分拆数，再减去1（排除仅含N本身的单个元素组合，和你给出的示例规则对齐），用动态规划可以将复杂度降到多项式级别：

动态规划实现（仅计数，效率最高） #

def solution(N):
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1, N + 1):
        # 从后往前遍历避免重复使用同一个数值
        for j in range(N, i - 1, -1):
            dp[j] += dp[j - i]
    # 减去仅包含N本身的单元素组合
    return dp[N] - 1

res = solution(50)
print(res)

该方案时间复杂度为O(N²)，空间复杂度为O(N)，N=200时可以秒出结果，N=1000也仅需几毫秒。

如果需要输出所有符合要求的组合而非仅计数，可以用带剪枝的递归回溯实现，完全不依赖第三方库：

def get_all_combinations(N):
    res = []
    def backtrack(remaining, max_allowed, path):
        if remaining == 0:
            # 排除长度为1的单元素组合
            if len(path) >= 2:
                res.append(path.copy())
            return
        # 下一个数必须小于前一个数，且不超过剩余需要凑的数值
        for num in range(min(max_allowed - 1, remaining), 0, -1):
            path.append(num)
            backtrack(remaining - num, num, path)
            path.pop()
    backtrack(N, N, [])
    return res, len(res)

# 测试输入8
combs, count = get_all_combinations(8)
print(count) # 输出5，和示例对齐
print(combs) # 输出[[7, 1], [6, 2], [5, 3], [5, 2, 1], [4, 3, 1]]

该方案通过剪枝避免了大量无效路径，效率远高于暴力枚举，N=50时也可以快速输出所有组合。

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