如何统计从1到n中选取k个数且和为n的所有组合数量？

你提到用itertools.combinations在大数据量下性能极差，这是因为该方法会生成所有可能的k元组合再过滤，而组合数C(n,k)会随n和k增长呈指数级爆炸（比如n=100、k=10时，组合数超过17万亿），完全无法处理。

这个问题本质是整数分拆问题：计算将n分拆为k个不同正整数的分拆数，我们可以用动态规划或递归记忆化的方法高效解决，时间复杂度为O(k*n)，远优于暴力枚举。

核心思路与递推公式 #

我们将问题分解为两种互斥的子情况：

1. 组合包含数字1：剩下的k-1个不同数字都≥2，它们的和为n-1。将这k-1个数字各减1，得到k-1个不同的正整数，和为n-1-(k-1) = n-k。这部分的组合数等于「将n-k分拆为k-1个不同正整数的组合数」。
2. 组合不包含数字1：所有k个数字都≥2，将每个数字减1，得到k个不同的正整数，和为n-k。这部分的组合数等于「将n-k分拆为k个不同正整数的组合数」。

递推公式：

count(k, n) = count(k-1, n-k) + count(k, n-k)

边界条件 #

• 若n < k*(k+1)//2：k个不同正整数的最小和是1+2+…+k = k(k+1)//2，若n小于该值，无有效组合，返回0。
• 若k=1：只有选n本身这一种组合，返回1（当n≥1时）。
• 若k=0且n=0：空组合，返回1；其他情况返回0。

实现方式 #

1. 递归记忆化（简洁易懂） #

用functools.lru_cache缓存计算结果，避免重复递归：

from functools import lru_cache

def count_valid_combinations(n, k):
    min_required_sum = k * (k + 1) // 2
    # 边界条件判断
    if n < min_required_sum:
        return 0
    if k == 1:
        return 1
    if k == 0:
        return 1 if n == 0 else 0
    
    return count_valid_combinations(n - k, k - 1) + count_valid_combinations(n - k, k)

测试示例：count_valid_combinations(10,3)返回4，与题目中的示例结果一致。

2. 二维动态规划（稳定可靠） #

用二维数组存储中间结果，避免递归的栈溢出问题，适合更大的n和k：

def count_valid_combinations_dp(n, k):
    min_required_sum = k * (k + 1) // 2
    if n < min_required_sum:
        return 0
    
    # dp[i][j] = 用i个不同正整数和为j的组合数
    dp = [[0] * (n + 1) for _ in range(k + 1)]
    dp[0][0] = 1  # 基准情况：0个数和为0
    
    for i in range(1, k + 1):
        current_min_sum = i * (i + 1) // 2
        for j in range(current_min_sum, n + 1):
            # 两种子情况的组合数之和
            dp[i][j] = dp[i-1][j - i] + dp[i][j - i]
    
    return dp[k][n]

测试示例：count_valid_combinations_dp(10,3)返回4，正确。

3. 一维动态规划（空间优化） #

观察到计算dp[i][j]只需要上一轮的dp[i-1][...]和当前轮的dp[i][...]，可以用一维数组优化空间：

def count_valid_combinations_optimized(n, k):
    min_required_sum = k * (k + 1) // 2
    if n < min_required_sum:
        return 0
    
    # prev_dp存储i-1个数字的组合数结果
    prev_dp = [0] * (n + 1)
    prev_dp[0] = 1
    
    for i in range(1, k + 1):
        curr_dp = [0] * (n + 1)
        current_min_sum = i * (i + 1) // 2
        for j in range(current_min_sum, n + 1):
            curr_dp[j] = prev_dp[j - i] + curr_dp[j - i]
        prev_dp = curr_dp
    
    return prev_dp[n]

测试示例：count_valid_combinations_optimized(10,3)返回4，正确。

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