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

<p>The legacy report has an end sum number of 200,000.</p>

<p>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).  </p>

<p>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?  </p>

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

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

<p>Not sure.  Any ideas?  Anyone ever done anything like this?   </p>

<p><strong>Additional Details:</strong><br>
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..?)</p>

<p>below is where I am at:</p>

<p>Below seems to give correct results, although it seems it will take awhile.  </p>

<p>I'll accept the answer above and let this run over night. </p>

<p>Thanks, </p>

<pre><code>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" ) )
</code></pre>
