基于给定数字列表统计目标值X加法组合数的实现方法
问题本质与核心思路
你要实现的是无约束正整数求和的不重复组合计数,也就是经典的「无界硬币找零组合数」问题——允许每个基准数字被重复使用、不区分组合内元素的排列顺序、统计总和等于目标值的所有合法组合总数。
很多之前你找到的代码运行结果不对,核心原因是混淆了「排列计数」和「组合计数」:把2+1和1+2当成了两种不同的组合,导致结果远大于预期。
动态规划实现的核心逻辑
我们用动态规划来做高效计数,关键是通过固定遍历顺序从根源上避免重复计数:
- 定义状态:
dp[s]表示用当前已经纳入统计范围的基准数字,凑出总和s的不重复组合总数。 - 初始边界:
dp[0] = 1,也就是凑出总和0只有1种合法方式——不选择任何数字,这是所有递推的基础。 - 关键遍历规则:先按顺序遍历每一个基准数字,再从小到大遍历从当前数字值到目标值的所有可能和。这个顺序可以保证我们永远只会统计「由已处理过的基准数字构成的组合」,不会出现同一组元素换个顺序就被重复计数的问题。
- 递推公式:对于当前遍历到的基准值
coin,所有大于等于coin的和s,满足dp[s] = dp[s] + dp[s - coin]。这个公式的含义是:凑s的组合总数,等于之前已有的组合数(完全不使用当前coin的情况),加上所有在凑s - coin的组合末尾追加一个coin得到的新组合数(使用当前coin的情况)。
可直接运行的Python实现
首先做必要的输入预处理:过滤掉非正的基准值(否则会导致组合数无限膨胀)、对重复的基准值去重(避免把同一个数字当成两个独立面额多算结果):
def calculate(target, denominations): # 预处理:过滤非正数值、去除重复面额 valid_coins = list(set(coin for coin in denominations if coin > 0)) # 初始化dp数组,索引对应目标和,值对应组合数 dp = [0] * (target + 1) dp[0] = 1 # 边界值 # 严格按「先遍历面额、再遍历和」的顺序递推 for coin in valid_coins: for current_sum in range(coin, target + 1): dp[current_sum] += dp[current_sum - coin] return dp[target]
测试验证
直接运行你给出的两个测试用例,结果完全匹配预期:
>>> calculate(5, (1,2,5)) 4 >>> calculate(42, (1,2,5,10,20)) 271
可以手动验证第一个用例的计数逻辑,和你列出的4种合法组合完全对应,没有重复也没有遗漏。
这个实现的时间复杂度为O(目标值 * 有效基准数),空间复杂度为O(目标值),就算目标值达到几千、几万也能快速计算,比递归枚举所有组合的效率高几个量级。
说明:如果后续需求调整为「每个基准数字只能使用一次」,只需要把内层遍历和的方向反过来(从目标值倒序遍历到当前面额)即可,逻辑是完全通用的。
内容的提问来源于stack exchange,提问作者Lulzsec
相关产品推荐
相关产品推荐

