求给定硬币列表及数量列表的不同硬币组合和的个数

我明白这个问题困扰你好几天了，咱们一步步来拆解它。核心目标是计算所有非空硬币组合能产生的不同总和的数量（毕竟示例里没有空组合）。

思路解析 #

你提到的用集合存不同和的思路完全可行，关键是要选对遍历更新的方式，避免重复计算或者遗漏。这里推荐一种迭代更新集合的直观方法：

1. 初始化一个集合，先放入0（代表选0个硬币的空组合，最后要减去这个情况）。
2. 逐个处理每种硬币：针对当前集合里的每个已有总和，尝试添加0到对应数量的当前硬币，把新生成的总和加入临时集合。
3. 用临时集合替换原集合，继续处理下一种硬币。
4. 最终集合的大小减1就是答案（减去空组合的0）。

拿你给的示例coins = [10,50,100]，quantity = [1,2,1]走一遍流程：

• 初始集合：{0}
• 处理10（数量1）：新集合变成{0,10}
• 处理50（数量2）：新集合变成{0,10,50,60,100,110}
• 处理100（数量1）：新集合变成{0,10,50,60,100,110,150,160,200,210}
• 最后集合大小是10，减1得到9，和示例结果完全一致。

代码实现（Python） #

def count_unique_sums(coins, quantity):
    sums = {0}
    for coin, qty in zip(coins, quantity):
        temp_set = set()
        # 对每个已有总和，尝试添加0到qty个当前硬币
        for current_sum in sums:
            for count in range(qty + 1):
                temp_set.add(current_sum + coin * count)
        sums = temp_set
    # 减去空组合的情况
    return len(sums) - 1

# 测试示例
coins = [10, 50, 100]
quantity = [1, 2, 1]
print(count_unique_sums(coins, quantity))  # 输出9

优化小提示 #

如果硬币面值或数量很大，上面的集合方法可能效率偏低，这时候可以用动态规划的思路，用布尔数组记录哪些总和是可达的，空间和时间效率会更高：

def count_unique_sums_dp(coins, quantity):
    max_possible_sum = sum(coin * qty for coin, qty in zip(coins, quantity))
    # dp数组：dp[s]表示总和s是否能被组合出来
    dp = [False] * (max_possible_sum + 1)
    dp[0] = True  # 空组合初始为可达
    
    for coin, qty in zip(coins, quantity):
        # 从后往前更新，避免重复计算同一硬币的多次添加
        for current_sum in range(max_possible_sum, -1, -1):
            if dp[current_sum]:
                for count in range(1, qty + 1):
                    new_sum = current_sum + coin * count
                    if new_sum > max_possible_sum:
                        break
                    dp[new_sum] = True
    # 统计所有可达的总和，减去空组合的dp[0]
    return sum(dp) - 1

这个方法在处理大数值场景时表现更优，因为数组操作比集合的哈希操作更快。

内容的提问来源于stack exchange，提问作者Stefan Lin