Python程序：整数拆分为r个正整数之和的非递归实现优化

原递归代码的缓存未生效是导致n>20后速度慢的核心原因之一——cache定义在函数内部，每次调用f(n,r)都会重新创建空缓存，完全无法复用之前计算的结果。不过既然你要求非递归实现，下面提供两种高效的方案：

方案一：迭代式动态规划 #

动态规划的核心是用迭代方式逐步构建拆分结果，避免递归的栈开销，同时复用之前的计算结果。

思路 #

• 定义prev_dp[m]为将整数m拆分为k-1个正整数的所有有序拆分方式；
• 从k=2迭代到k=r，每次计算curr_dp[m]（拆分为k个正整数的方式）：遍历可能的最后一个数i，将prev_dp[m-i]的所有拆分结果末尾追加i，即可得到curr_dp[m]；
• 边界处理：n < r时无有效拆分；r=1时仅有[[n]]一种方式。

代码实现 #

def split_into_r_positive_integers(n, r):
    # 边界情况：无法拆分的场景
    if n < r:
        return []
    if r == 1:
        return [[n]]
    
    # 初始化：拆分为1个正整数的所有情况
    prev_dp = [[] for _ in range(n + 1)]
    for m in range(n + 1):
        prev_dp[m] = [[m]]
    
    # 迭代计算拆分为2到r个正整数的情况
    for k in range(2, r + 1):
        curr_dp = [[] for _ in range(n + 1)]
        # 拆分为k个正整数时，m至少为k（每个数至少1）
        for m in range(k, n + 1):
            # 最后一个数i的范围：1 <= i <= m - (k-1)（剩余k-1个数至少和为k-1）
            max_i = m - (k - 1)
            for i in range(1, max_i + 1):
                # 遍历拆分为k-1个数的所有结果，追加i后加入当前结果
                for split in prev_dp[m - i]:
                    curr_dp[m].append(split + [i])
        # 更新为下一次迭代的前置结果
        prev_dp = curr_dp
    
    return prev_dp[n]

优化说明 #

该版本仅保留前一轮的计算结果，空间复杂度从O(r*n*S)（S为拆分方式数量）优化为O(n*S)，对于大n和r更高效。

方案二：非递归回溯法 #

通过栈模拟递归的回溯过程，手动维护当前的拆分状态，避免递归调用的开销。

思路 #

• 用栈保存当前状态：已选数的个数、当前累加和、当前拆分列表；
• 从第一个数为1开始，逐步尝试所有可能的后续数字，确保剩余数字能满足“r个正整数”的要求（剩余数字的和至少等于剩余个数）；
• 当已选满r个数且和为n时，将当前拆分列表加入结果。

代码实现 #

def split_into_r_positive_integers_backtrack(n, r):
    if n < r:
        return []
    if r == 1:
        return [[n]]
    
    result = []
    # 栈元素：(已选数的数量, 当前累加和, 当前拆分路径)
    stack = [(1, 1, [1])]
    
    while stack:
        count, current_sum, path = stack.pop()
        remaining_count = r - count
        remaining_sum = n - current_sum
        
        # 已选满r个数，检查和是否为n
        if remaining_count == 0:
            if current_sum == n:
                result.append(path)
            continue
        
        # 下一个数的最大可能值：剩余和减去剩余个数-1（保证剩下的数至少为1）
        max_next = remaining_sum - (remaining_count - 1)
        # 从大到小入栈，保证结果顺序和递归版本一致（可选调整）
        for num in range(max_next, 0, -1):
            stack.append((count + 1, current_sum + num, path + [num]))
    
    # 若需要和原递归代码的顺序完全一致，可反转结果
    # result.reverse()
    return result

测试示例 #

比如调用split_into_r_positive_integers(4, 3)，会返回：

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

和原递归代码的输出一致。

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