查找dict中可重复选取的键组合使其值之和等于目标值及代码优化

• 浮点数精度错误：你用==判断浮点数相等本身不符合浮点数的运算特性，累加过程中会产生精度误差，比如1.04 * 3在Python中实际运算结果是3.1200000000000006，和目标值3.12做相等判断会返回False，导致即使总和理论上等于目标值，也无法触发匹配条件，递归无法正常终止。
• 递归分支爆炸：当前写法允许每次递归遍历所有键，会产生大量顺序不同的重复组合（比如["a","b"]和["b","a"]都会被当成有效结果返回），当目标值为199.45时，递归的分支数呈指数级增长，自然会长时间无输出。
• 缺少提前剪枝：原代码只有总和超过目标值才返回，没有利用排序提前终止无效遍历，进一步拖慢了运行效率。

1. 转整数规避精度问题 #

把所有值和目标值都乘以100（你给出的示例值都是两位小数，乘100刚好可转为整数），用整数做相等判断，彻底解决精度问题。如果你的实际数据有更多位小数，对应乘以10的n次方即可。

2. 调整递归逻辑避免重复组合 #

递归时仅遍历当前索引及之后的键，保证组合内元素的顺序和原字典排序一致，不会生成顺序不同的重复组合。

3. 排序+提前剪枝 #

先把键值对按值从小到大排序，递归时如果当前值已经大于剩余目标值，后面更大的值不需要再遍历，直接剪枝即可。

def combination_sum(data, target):
    # 转换为整数避免浮点精度问题，适配两位小数的数值
    items = [(key, int(value * 100)) for key, value in data.items()]
    # 按数值从小到大排序，用于后续剪枝
    items.sort(key=lambda x: x[1])
    target_int = int(target * 100)
    result = []

    def backtrack(start_idx, remain_target, current_path):
        if remain_target == 0:
            result.append(current_path.copy())
            return
        for i in range(start_idx, len(items)):
            current_key, current_val = items[i]
            # 当前值已经大于剩余目标，后续值更大，直接剪枝
            if current_val > remain_target:
                break
            current_path.append(current_key)
            # 递归时传入当前索引i，允许重复选当前元素，且不会回头选之前的元素避免重复组合
            backtrack(i, remain_target - current_val, current_path)
            current_path.pop()
    
    backtrack(0, target_int, [])
    return result

# 调用测试
a = {"a" : 1.04, "b" : 1.07, "c" : 10.99}
# 测试小目标值
print(combination_sum(a, 3.12))
# 输出：[['a', 'a', 'a']]
# 测试目标值199.45
print(combination_sum(a, 199.45))

这个问题本质是无界组合求和问题，属于NP完全问题，如果你的可选值数量多、目标值非常大，没有多项式时间的最优解法，上述优化已经是常规场景下效率最高的实现方式。

内容的提问来源于stack exchange，提问作者Jonas Palačionis