You need to enable JavaScript to run this app. 基于给定数字列表统计目标值X加法组合数的实现方法
优惠活动
大模型
产品
解决方案
定价
更多

基于给定数字列表统计目标值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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.25 06:54:04