c# - 找到正确数字集的算法

Question

我将采用 python 或 c# 解决方案

我有大约 200 个数字:

 19.16 
 98.48 
 20.65 
 122.08 
 26.16 
 125.83 
 473.33 
 125.92 
 3,981.21 
 16.81 
 100.00 
 43.58 
 54.19 
 19.83 
 3,850.97 
 20.83 
 20.83 
 86.81 
 37.71 
 36.33 
 6,619.42 
 264.53 
...
...

我知道在这组数字中，有一个数字组合可以加起来等于某个数字，假设它是 2341.42

我如何找出哪些数字组合相加？

我正在帮助会计人员追踪正确的数字

Answer 1

这是 Python 中的一个递归函数，它将找到任何大小的所有解决方案，只有两个参数(您需要指定)。

def find_all_sum_subsets(target_sum, numbers, offset=0):
    solutions = []
    for i in xrange(offset, len(numbers)):
        value = numbers[i]
        if target_sum == value:
            solutions.append([value])
        elif target_sum > value:
            sub_solutions = find_all_sum_subsets(target_sum - value, numbers, i + 1)
            for sub_solution in sub_solutions:
                solutions.append(sub_solution + [value])
    return solutions

它在这里工作:

>>> find_all_sum_subsets(10, [1,2,3,4,5,6,7,8,9,10,11,12])
[[4, 3, 2, 1], [7, 2, 1], [6, 3, 1], [5, 4, 1], [9, 1], [5, 3, 2], [8, 2], [7, 3], [6, 4], [10]]
>>>