我们可以不对从10^(digs-1)到10^digs的每一个数字进行迭代，这样会有一个很宽的搜索空间，我们可以通过从最左边的数字到最右边的数字以非递减的方式（或者如果你喜欢的话，从右到左以非递增的方式）一个接一个地添加数字来进行迭代。Reference
我在网站上测试了下面的python代码，它似乎解决了这个任务。
我认为这段代码的时间复杂度还可以改进。
如果你想优化它，你可以尝试搜索自顶向下的动态规划和记忆技术。

def find_all(sum_dig, digs):
    global total_count, lowest_value, greatest_value
    
    total_count = 0
    lowest_value = -1
    greatest_value = -1
    
    # complete search via depth first search
    def dfs(digit_sum, digit_count, num, digit_from):
        global total_count, lowest_value, greatest_value
        
        # base case
        if digit_count == digs:
            if digit_sum == sum_dig:
                if lowest_value == -1:
                    lowest_value = num
                greatest_value = num
                total_count += 1
            return
        
        # try all possible values one by one
        for i in range(digit_from, 10):
            dfs(digit_sum + i, digit_count + 1, num * 10 + i, i)
    
    dfs(0, 0, 0, 1)
    
    answer = []
    if total_count > 0:
        answer = [total_count, lowest_value, greatest_value]
    return answer

下面是我对每个所需值的函数，它似乎通过了测试（如果分区计数为零，则返回空列表）。
对于结果的数目，我们可以修改具有受限部分数目的划分的递归：取（1）将n-k划分为具有至多l-1的最大部分的k部分的所有分区的计数，并将其相加（2）将n-1划分为具有至多l的最大部分的k-1部分的所有划分的计数。（对于（1）中的每个部分添加1，总共k1 s。对于（2）中的每个分区，添加一个部分1。）O(n, k)搜索空间。

def f(n, k, l, memo={}):
  if k == 0 and n == 0:
    return 1

  if n <= 0 or k <= 0 or l <= 0:
    return 0

  if (n, k, l) in memo:
    return memo[(n, k, l)]

  memo[(n, k, l)] = f(n - k, k, l-1, memo) + f(n - 1, k - 1, l, memo)

  return memo[(n, k, l)]

对于最小的数字，我们可以从左到右使用贪婪的O(n)方法，总是选择最小的数字。

def g(n, k):
  if k == 0:
    return 0

  next_digit = max(1, n - 9 * (k - 1))

  return next_digit * 10 ** (k - 1) + g(n - next_digit, k - 1)

对于最大的，我想不出比递归更好的方法了，递归根据当前状态限制数字的选择。O(n, k).bb1commentedO(n)解决方案。

from math import ceil

def h(n, k, largest):
  if n < 0:
    return 0

  if k == 1:
    return n

  best = 0
  digit = 0
  
  for i in range(
    min(largest, n - k + 1),
    min(largest, ceil(n / k)) - 1,
    -1):
    candidate = h(n - i, k - 1, i)
    if candidate > best:
      best = candidate
      digit = i

  return digit + 10 * best

你可以使用递归的方法，一次收集一个数字到一个列表中，直到它达到指定的总和，如果它的总和正确匹配，返回值。然后，我们可以大量使用过滤来避免测试我们知道将超过目标总和或不是按升序排列的数字，减少我们必须大量检查的潜在值的数量。
我在网站上测试过，它确实在规定的时间内通过了所有测试。
find_all函数只接受结果并将其转换为质询所需的格式。

def find_all(sum_dig, digs):
    result = find_count(sum_dig, digs, [])
    size, sm, lg = len(result), min(result), max(result)
    return [size, sm, lg]

def find_count(sum_dig, digs, lst=[]):
    if len(lst) == digs:
        if sum(lst) == sum_dig:
            return [int(''.join([str(i) for i in lst]))]
        return []
    combos = []
    start = 1 if not len(lst) else lst[-1]
    for i in range(start, 10):
        t = 0 if not lst else sum(lst)
        if t + i <= total:
            combos += find_count(sum_dig, digs, lst + [i])
    return combos

找出所有给予总和等于s的数

m, s = map(int, input('').split(' ')) # m: length , s : sum of digits
result = []

counter = 0
def getSum(n):
    sum = 0
    while (n != 0):
        sum = sum + (n % 10)
        n = n // 10
    return sum

for i in range((10 ** (m - 1)), (10 ** m)):
    r = getSum(i)
    if r == s:
       counter += 1
       result.append(i)

print(counter, result)