find all elements in a list of positive numbers that add up to number X
Question: I'm trying to reverse engineer a legacy report and using python to solve the
problem.

The legacy report has an end sum number of 200,000.

I know a collection of the numbers that could end up to this 200k, but this
collection is littered with many other numbers that are to be filtered out
(with logic i'm yet to understand).

In python, How could i iterate through the list of numbers to find all entries
(sub-lists) of variable length (could be 1 element that = 200k, or the product
of 15 elements...) that would add up to the 200k?

I started to write it out, then decided to ask for help when i realized
element #1 + 2 could overflow but list element #1 + 4 + 7 could be a match to
the 200k....

It's almost like factorization, however with the sum's instead of the
products, and within a list of possible candidates.

Not sure. Any ideas? Anyone ever done anything like this?

**Additional Details:**  
With permutations and numpy i'm getting a result as expected, however it is
taking far too long with the expected inputs and outputs. (i.e. days..?)

below is where I am at:

Below seems to give correct results, although it seems it will take awhile.

I'll accept the answer above and let this run over night.

Thanks,

    
    
    from itertools import permutations 
    import numpy , pickle, random
    output_results = {} 
    input_array = [random.randrange(0,15000) for i in range(1000)]
    desired_sum = 200000
    #input_array = (1,2,9,13,12) 
    #desired_sum = 23 
    
    for r in range(1,len(input_array)): 
        for p in permutations(input_array, r):
            temp_sum = numpy.sum(p) 
            if temp_sum == desired_sum: 
                output_results[p] = numpy.sum(p) 
        if r % 10 == 0:
            print "Finished up to number %s " % r 
    
    pickle.dump( output_results, open( "save.p", "wb" ) )
    


Answer: [Itertools.permutations](http://docs.python.org/2/library/itertools.html#itertools.permutations)
can help.

Varying the value of `r` in `permutations(iterable, r)` you can try to find
all the possible permutations containing `r` entries from `iterable` (your
collection), of which you can easily get sums (e.g. with `numpy.sum`).

If you have some idea of what to expect and set a reasonable upper limit for
`r` you should get an answer in a reasonable time

**edit**

@joefromct: you can first estimate the largest value of `r` needed to find the
solution you want in the following way (is not tested, but the idea should be
correct)

    
    
    sorted_input = np.sorted(input_array)
    cumsum = np.cumsum(sorted_input)
    max_r = (cumsum<desired_sum).sum()
    if max_r == len(input_array) and sorted_input[-1] < desired_sum:
        print("sorry I can't do anything for you")
        exit()
    
    for r in range(1,max_r):
        [...]
    

