# Series calculation

I have some random integers separated by space read from a text file like

99 20 30 1 100 400 5 10


I have to find a sum from any combination of these integers that is closest to a specifiq number like

183


what is the fastest and accurate way of doing this?

-
I guess this is similar to the subset sum problem: en.wikipedia.org/wiki/Subset_sum_problem – PEV Jan 26 '11 at 19:26
Here is a similar question: stackoverflow.com/questions/2070359/… – PEV Jan 26 '11 at 19:28
Exact copy by same person: stackoverflow.com/questions/4808503/series-calculation – Aryabhata Jan 26 '11 at 23:21

The non-trivial algorithm takes $2^{n/2}$ time and memory. Divide the list into two parts and calculate all the internal sums. Sort both lists, put one pointer at the low end of one list, and another at the high end of the other list. Advance the second pointer until the sum crosses the target. Then advance the first pointer, and repeat. Maintain the "best sum encountered so far", and once the first pointer is done traversing the list, you have the optimum in your hands.