如何计算n个1-9单数字整数和为S的不同组合数？

问题分析 #

你要解决的是有序组合问题（顺序不同算不同组合，比如(1,2,5)和(2,5,1)是两个独立的解），核心是统计n个取值在1-9之间的整数，和为S的所有有序排列数量。

方法思路：动态规划 #

动态规划是解决这类计数问题的高效方法，无需暴力枚举所有可能，而是通过状态转移逐步推导结果：

状态定义 #

定义dp[i][j]表示用i个数字，和为j的有序组合数。

初始状态 #

当i=1时，只有单个数字的情况：如果j在1-9之间，dp[1][j] = 1（只有1种方式取这个数字）；否则dp[1][j] = 0。

状态转移 #

对于i>1的情况，第i个数字可以取1-9中的任意值k，那么前i-1个数字的和必须是j - k。因此：

dp[i][j] = 总和( dp[i-1][j - k] )，其中k ∈ [1,9]，且j - k ≥ i-1（前i-1个数字和至少为i-1，每个数字≥1），j - k ≤ 9*(i-1)（前i-1个数字和最多为9*(i-1)，每个数字≤9）

边界判断 #

如果S < n（n个数字最小和为n，每个取1）或者S > 9*n（n个数字最大和为9n，每个取9），直接返回0，没有符合条件的组合。

代码实现（Python） #

以下是简单易懂的实现，适合编程基础不多的用户：

def count_combinations(n, S):
    # 先判断边界情况
    if S < n or S > 9 * n:
        return 0
    
    # 初始化dp数组，dp[i][j]表示i个数字和为j的组合数
    dp = [[0]*(9*n + 1) for _ in range(n+1)]
    
    # 初始状态：1个数字的情况
    for k in range(1, 10):
        dp[1][k] = 1
    
    # 填充dp数组
    for i in range(2, n+1):
        # i个数字的和j的范围是i到9*i
        for j in range(i, 9*i + 1):
            # 第i个数字可以取1-9，只要j - k >= i-1（前i-1个数字的最小和是i-1）
            for k in range(1, 10):
                prev_sum = j - k
                if prev_sum >= i-1 and prev_sum <= 9*(i-1):
                    dp[i][j] += dp[i-1][prev_sum]
    
    return dp[n][S]

# 验证你的例子：n=3，S=7
print(count_combinations(3,7))  # 输出15，对应所有有序组合

优化说明（可选） #

上面的代码用了二维数组，空间复杂度是O(n*S)。如果想节省空间，可以用滚动数组，因为计算dp[i]只需要dp[i-1]的数据，把二维数组改成一维数组即可：

def count_combinations_optimized(n, S):
    if S < n or S > 9 * n:
        return 0
    
    # 滚动数组，prev_dp表示i-1个数字的组合数，curr_dp表示i个数字的
    prev_dp = [0]*(9*n +1)
    for k in range(1,10):
        prev_dp[k] =1
    
    for i in range(2, n+1):
        curr_dp = [0]*(9*n +1)
        for j in range(i, 9*i +1):
            for k in range(1,10):
                prev_sum = j -k
                if prev_sum >= i-1 and prev_sum <=9*(i-1):
                    curr_dp[j] += prev_dp[prev_sum]
        prev_dp = curr_dp
    
    return prev_dp[S]

为什么暴力法不可行 #

暴力法需要枚举所有n个1-9数字的排列，总共有9^{n种可能。当n=10时，9}10≈3.48亿，计算量极大，普通电脑根本跑不完；而动态规划的时间复杂度是O(nS9)，比如n=10，S=45，只需要计算10459=4050次操作，效率天差地别。

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