如何修改Python递归代码仅输出指定位数的数字组合?
固定长度组合输出的修改方案
原代码基础逻辑
原递归代码实现的功能是生成所有由1到n的数字组成、非降序排列、元素总和恰好为n的组合,核心参数的实际含义:
i:当前循环可选的最小数字,用来保证组合非降序,避免生成重复的排列结果n:当前递归分支下,剩余需要凑齐的目标和值out:存储当前正在生成的组合的缓存数组index:当前已经填充到out里的元素个数
具体修改步骤
要实现仅输出指定位数的组合,不需要改动核心的递归遍历逻辑,只需要新增长度校验规则和对应的剪枝优化即可:
- 给递归函数新增入参
target_len,传入需要匹配的组合固定长度 - 在命中“剩余和为0”的打印分支里,增加判断条件:只有当前已经填充的元素个数
index等于target_len时,才执行打印 - 增加无效分支剪枝,减少没必要的递归计算:
所有组合元素都是正整数,若当前已填充index个元素,剩余的target_len - index个位置最少需要凑出target_len - index的和(每个位置填1)。如果当前剩余需要凑的和值小于这个最小值,直接终止当前分支的递归即可。
修改后的完整代码
# 新增target_len参数,指定要输出的组合的固定长度 def printCombinations(i, n, out, index, target_len): # 剪枝:剩余需要凑的和,甚至不够填剩余位置的1,直接终止分支 remaining_slots = target_len - index if n < remaining_slots: return # 已经凑够总和,且组合长度刚好等于目标值,才打印 if n == 0 and index == target_len: print(out[:index]) return for j in range(i, n + 1): out[index] = j printCombinations(j, n - j, out, index + 1, target_len) if __name__ == '__main__': n = 5 target_len = 5 # 按需修改为需要的组合长度,比如要打印5位组合就设为5 out = [None] * n printCombinations(1, n, out, 0, target_len)
效果说明
- 按示例设置
n=5、target_len=5时,因为5个非降序正整数相加和为5,唯一符合要求的结果是[1, 1, 1, 1, 1],完全实现“仅打印5位数字组合”的需求 - 比如要取长度为3的组合,把
target_len改为3,程序就只会输出所有长度为3、元素和为5的非降序组合:[1, 1, 3]、[1, 2, 2],其他长度的结果都会被自动过滤掉
内容的提问来源于stack exchange,提问作者therealrondon
相关产品推荐
相关产品推荐

