c# - algorithm to find the correct set of numbers

Question

i will take either python of c# solution

i have about 200 numbers:

 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 
...
...

i know that in this set of numbers, there is a combination of numbers that will add up to a certain number let's say it is 2341.42

how do i find out which combination of numbers will add up to that?

i am helping someone in accounting track down the correct numbers

Answer 1

Here's a recursive function in Python that will find ALL solutions of any size with only two arguments (that you need to specify).

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

Here it is working:

>>> 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]]
>>>