Combination Sum IV与硬币找零计数问题的核心区别

两个问题的规则与示例对比 #

• Combination Sum IV（组合总和IV）
  问题规则：给定由不同整数组成的数组nums和目标整数target，返回元素和等于target的序列总数，元素顺序不同的序列视为不同结果。
  标准示例：输入nums = [1,2,3]、target = 4时，输出为7，对应合法序列为：
  (1, 1, 1, 1)、(1, 1, 2)、(1, 2, 1)、(1, 3)、(2, 1, 1)、(2, 2)、(3, 1)

• Coin Change（无界硬币找零计数）
  问题规则：给定无限供应的不同面额硬币集合，计算凑出目标面值的方案总数，不区分硬币选取顺序，同面额组合仅计1次。
  采用和上述示例完全相同的输入（硬币面额[1,2,3]、目标面值4）时，输出仅为4，对应合法方案为：
  (1,1,1,1)、(1,1,2)、(1,3)、(2,2)

核心差异本质：排列计数与组合计数的区别 #

两个问题都属于元素可重复选取的无界计数场景，状态转移方程完全一致，唯一的区别来自动态规划的两层循环遍历顺序，最终分别统计排列数和组合数：

1. 硬币找零：统计不考虑顺序的组合数 #

标准无界背包解法采用外层遍历硬币面额、内层从小到大遍历目标面值的顺序，核心代码片段如下：

dp = [0] * (target + 1)
dp[0] = 1
# 先遍历所有硬币面额
for coin in coins:
    # 再从小到大遍历可凑出的面值
    for i in range(coin, target + 1):
        dp[i] += dp[i - coin]

这种遍历逻辑下，硬币只会按照固定的遍历顺序被选取，比如永远只会出现「先选1、再选2」的组合，不会出现「先选2、再选1」的重复计数，最终得到的就是不考虑顺序的组合总方案数。

2. 组合总和IV：统计考虑顺序的排列数 #

如果需要把顺序不同的序列计为不同结果，只需要调换两层循环的顺序，采用外层遍历目标和、内层遍历所有可选数字的逻辑，核心代码片段如下：

dp = [0] * (target + 1)
dp[0] = 1
# 先遍历所有需要凑的目标和
for i in range(1, target + 1):
    # 再遍历所有可选数字，考虑每个数字放在当前位置的情况
    for num in nums:
        if i >= num:
            dp[i] += dp[i - num]

这种遍历逻辑下，对于每一个目标和，都会依次尝试把每个可选数字放在序列的当前位置，比如凑和为3时，既会计算「选1之后凑剩余2」的所有方案，也会计算「选2之后凑剩余1」的方案，自然就把(1,2)和(2,1)计为两个独立结果，最终得到的是排列总方案数。

一句话总结：两个问题没有本质的模型差异，只是遍历顺序的选择决定了是否对不同选取顺序的结果重复计数，分别对应排列和组合两种统计需求。

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