求高效解法：找出数字和为K的N位有序数字的统计结果

给定数字和K（sum_dig）与位数N（digs），需要找出所有满足以下条件的数字的数量、最小值和最大值：

• 数字为N位（不能以0开头）
• 各位数字之和等于K
• 各位数字非递减（例如145符合，382不符合）

你的原代码通过遍历所有N位数字并逐个校验条件，时间复杂度为O(10^N)，当N较大时必然超时。以下是高效优化方案：

核心思路：直接构造符合条件的数字 #

无需遍历所有N位数字，而是通过数学转化和动态规划，直接生成/计算满足要求的结果，大幅降低计算量。

1. 边界条件快速判断 #

首先排除不可能存在结果的情况：

• 若sum_dig < digs：每位数字至少为1，总和最小为digs，不可能满足
• 若sum_dig > 9*digs：每位数字最大为9，总和最大为9*digs，不可能满足
  以上两种情况直接返回空列表。

2. 动态规划计算合法数字数量 #

将问题转化为整数分拆问题：统计用1-9的数字组成digs位、和为sum_dig的非递减数字组合数。
使用动态规划实现：

def calculate_count(sum_dig, digs):
    # dp[j][k] 表示j位数字、和为k的合法组合数
    dp = [[0] * (sum_dig + 1) for _ in range(digs + 1)]
    dp[0][0] = 1  # 初始状态：0位数字和为0的组合数为1
    
    for num in range(1, 10):
        # 倒序遍历避免重复计算同一数字的多次选取
        for j in range(digs, 0, -1):
            for k in range(num, sum_dig + 1):
                dp[j][k] += dp[j-1][k - num]
    return dp[digs][sum_dig]

3. 构造最小非递减数字 #

从高位到低位，优先选择最小的合法数字，保证剩余位数能用不小于当前数字的数凑出剩余和：

def build_min(sum_dig, digs):
    res = []
    remaining_sum = sum_dig
    remaining_digits = digs
    prev = 1  # 第一位至少为1
    
    while remaining_digits > 0:
        # 从最小可能的数字开始尝试
        for d in range(prev, 10):
            # 校验：当前数字*digs ≤ 剩余和 ≤9*digs（剩余位都取9的和）
            if d * remaining_digits <= remaining_sum <= 9 * remaining_digits:
                res.append(str(d))
                remaining_sum -= d
                remaining_digits -= 1
                prev = d
                break
    return int(''.join(res))

4. 构造最大非递减数字 #

从高位到低位，优先选择最大的合法数字，保证剩余位数能用不小于当前数字的数凑出剩余和：

def build_max(sum_dig, digs):
    res = []
    remaining_sum = sum_dig
    remaining_digits = digs
    prev = 1
    
    while remaining_digits > 0:
        # 从最大可能的数字开始尝试
        for d in range(9, prev-1, -1):
            if d * remaining_digits <= remaining_sum <= 9 * remaining_digits:
                res.append(str(d))
                remaining_sum -= d
                remaining_digits -= 1
                prev = d
                break
    return int(''.join(res))

5. 整合主函数 #

将上述模块整合，得到最终高效实现：

def find_all(sum_dig, digs):
    # 快速排除不可能的情况
    if sum_dig < digs or sum_dig > 9 * digs:
        return []
    
    count = calculate_count(sum_dig, digs)
    if count == 0:
        return []
    
    min_num = build_min(sum_dig, digs)
    max_num = build_max(sum_dig, digs)
    return [count, min_num, max_num]

效率说明 #

• 动态规划的时间复杂度为O(9 * digs * sum_dig)，即使digs=10、sum_dig=90，计算量仅为8100次，远低于原代码的指数级复杂度。
• 构造最小/最大数字的时间复杂度为O(digs * 9)，几乎可以忽略不计。

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