Python入门：如何统计用列表元素组合出指定数值的方式数

你要解决的是用给定列表中的元素（默认可重复使用）组合出目标数值的方式数量，这属于经典的「无界背包」问题变种，下面给你一步步拆解思路和实现代码。

核心思路 #

用递推逻辑简化问题：

• 定义dp[n]为组合出数值n的方式数量
• 对每个数值n，遍历列表里的每个元素num：
  • 若num <= n，则dp[n]可以累加dp[n - num]的数量（给所有能组合出n-num的方式末尾加一个num，就得到了组合出n的新方式）
• 边界条件：dp[0] = 1（和为0只有1种方式：什么元素都不选）

代码实现 #

方法1：动态规划（高效推荐） #

这是最适合实际使用的版本，避免重复计算，效率很高：

def count_combinations(nums, target):
    # 初始化dp数组，dp[i]存储和为i的组合方式数
    dp = [0] * (target + 1)
    dp[0] = 1  # 边界条件：和为0的组合仅空组合这1种
    
    # 从1到目标数依次计算每个数值的组合方式
    for i in range(1, target + 1):
        for num in nums:
            if num <= i:
                dp[i] += dp[i - num]
    
    return dp[target]

# 测试你的示例
nums = [1, 2, 3]
target = 10
print(count_combinations(nums, target))  # 输出14

方法2：递归（易理解但效率低） #

如果想先搞懂底层逻辑，可以先看这个版本（但计算大目标数时会重复计算，速度慢）：

def count_combinations_recursive(nums, target):
    if target == 0:
        return 1
    if target < 0:
        return 0
    total = 0
    # 遍历每个元素，累加剩余数值的组合方式数
    for num in nums:
        total += count_combinations_recursive(nums, target - num)
    return total

# 测试
print(count_combinations_recursive([1,2,3], 10))  # 同样输出14

额外补充：元素不可重复的情况 #

如果要求每个元素只能用一次，那就是「0-1背包」问题，只需修改动态规划的遍历顺序：

def count_combinations_unique(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    
    # 先遍历元素，再从目标数倒序遍历，避免重复使用同一元素
    for num in nums:
        for i in range(target, num - 1, -1):
            dp[i] += dp[i - num]
    
    return dp[target]

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