如何优化满足[1,K]范围的数字有序组合递归代码？

问题说明 #

给定数字字符串，需找出所有符合以下要求的数字组合：

1. 每个数字取值范围为[1, K]
2. 保持原字符串的数字顺序

示例：输入字符串为"123"、K=200时，有效组合共4种：[1, 2, 3]、[12, 3]、[1, 23]、[123]

以下是用户的尝试代码：

def findComb(stri):
    if len(stri) <= 1 :
        return [stri]
    arr=findComb(stri[1:len(stri)])
    destArr=[]
    for i in arr:
        destArr.append(stri[0]+i)
        destArr.append(stri[0]+','+i)
    return destArr


n, K=map(str,input().split())
K=int(K)
s=input()
l=findComb(s)
print(l)

lis=[]
for i in l:
    f=0
    if ',' in i:
        li=i.split(',')
        for j in li:
            if int(j)>K:
                f=1
                break
        if f==0:
            lis.append(li)
    else:
        if int(i)<=K:
            lis.append(i)

print(len(lis)%(10^9+7))

核心优化建议 #

• 放弃全组合生成后过滤的思路：当前代码先生成所有可能的分割字符串（指数级数量），再逐一校验有效性，当输入字符串较长时，内存占用和时间复杂度会急剧上升。建议改用动态规划直接统计有效组合数，或在递归时提前剪枝：比如当前拼接的数字超过K，就停止该分支的递归。
• 移除冗余的字符串拼接操作：findComb用逗号拼接字符串存储分割结果完全没必要，直接用列表传递分割后的数字（或子串），能大幅减少字符串操作的性能开销。
• 修复输入处理与取模错误：
  • 代码中读取的n未使用，可删除或用于校验输入字符串长度；
  • 10^9+7是Python的按位异或运算，正确的取模值应为10**9+7。
• 增加前导零校验：若原字符串包含前导零（如"012"），分割出的"01"这类数字不符合要求（不在[1,K]范围内），需添加判断：分割出的子串不能以"0"开头，除非子串本身就是"0"（但题目要求数字≥1，因此直接排除所有带前导零的子串）。
• 优化数字大小判断逻辑：将K转换为字符串，通过比较子串长度与K的字符串长度快速判断：若子串更长则直接无效；长度相同时再逐字符比较，避免大整数转换的性能损耗。

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