Python求解凑目标金额的最优硬币组合问题

嘿，我来帮你搞定这个找硬币子集凑目标金额的事儿！你遇到的其实是带重复元素的子集和问题——需要从给定的硬币列表里选出一个子集，它们的总和恰好等于目标金额，而且每个硬币只能用一次（毕竟列表里的每个元素都是实际存在的一枚硬币）。

核心思路：回溯法+剪枝优化 #

回溯法是解决这类“找具体组合”问题的常用方法，配合排序和去重剪枝，能高效找到可行解：

1. 先排序硬币列表：这样可以提前终止无效搜索（比如当前硬币加已选金额超过目标，后面更大的硬币直接不用看了），同时方便跳过重复硬币避免冗余搜索。
2. 回溯遍历：逐个尝试选择或不选当前硬币，记录已选硬币的路径和当前总和，当总和等于目标时，就得到了我们要的组合。

代码实现（Python） #

def find_target_coins(coins, total):
    # 排序硬币，便于剪枝和去重
    coins.sort()
    result = []
    
    def backtrack(start_idx, current_sum, selected_coins):
        # 找到符合条件的组合，保存并终止搜索
        if current_sum == total:
            result.append(selected_coins.copy())
            return True
        # 总和超过目标，直接返回
        if current_sum > total:
            return False
        
        for i in range(start_idx, len(coins)):
            # 跳过重复的硬币，避免生成重复组合
            if i > start_idx and coins[i] == coins[i-1]:
                continue
            # 当前硬币+已选总和超过目标，后面更大的硬币也不用看了
            if current_sum + coins[i] > total:
                break
            
            # 选择当前硬币
            selected_coins.append(coins[i])
            # 递归搜索，找到解就直接返回
            if backtrack(i + 1, current_sum + coins[i], selected_coins):
                return True
            # 回溯，撤销选择
            selected_coins.pop()
        
        return False
    
    backtrack(0, 0, [])
    # 返回找到的第一个可行组合，没有的话返回None
    return result[0] if result else None

# 测试示例1
test_coins_1 = [10, 10, 20, 20, 20, 100, 100]
test_total_1 = 250
print(find_target_coins(test_coins_1, test_total_1))  # 输出类似 [10, 20, 20, 100, 100]

# 测试示例2
test_coins_2 = [5, 5, 10, 20, 50, 100, 100, 200]
test_total_2 = 250
print(find_target_coins(test_coins_2, test_total_2))  # 输出比如 [50, 100, 100] 或其他可行组合

代码说明 #

• 排序剪枝：排序后，一旦发现当前硬币加上已选总和超过目标，直接break循环，因为后面的硬币面值更大，肯定也会超，不用再浪费时间。
• 去重处理：跳过和前一个硬币面值相同的元素，避免生成重复的组合（比如两个10分硬币，选第一个和选第二个得到的组合本质是一样的，顺序无关的话没必要重复搜索）。
• 提前终止：找到第一个可行组合后就立刻返回，不用继续搜索所有可能，适合只需要一个解的场景。如果需要所有可行组合，去掉return True的逻辑，让函数收集所有符合条件的路径即可。

内容的提问来源于stack exchange，提问作者Leo Whitehead