Find All Elements In A List Of Positive Numbers That Add Up To Number X

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

Solution 1:

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 inrange(1,max_r):
    [...]