Consider the following 3 totals:
65,232
73,002
56,273
For each total listed above, identify the three numbers from the following list which, when summed up, equal each total above.
41,207
33,749
27,641
25,921
24,790
20,348
18,905
18,686
12,797
11,447
There are 10*9*8 (720) possibilities - what is the fastest way to identify the three numbers for each total?
The number of possibilities is actually much lower, only $\frac{10\times9\times8}{3\times2\times1} = 120$, because it doesn't matter what order they come in; however, we can do some things to reduce the amount of work required: we can calculate the required smallest value based on the larger two values, and we can restrict the possible range of the larger values based on their order.
First things first: We know that the largest of the three numbers must be higher than $1/3$ the size of the target number. For $65\,232$ this means that we only need to check the first $5$ numbers for that, because anything smaller than $65\,232 / 3 = 21\,744$ can't possibly the largest number.
Now, considering each of these numbers in turn, we'll try $a = 41\,207$ and find the leftovers $65\,232-41\,207 = 24\,025$. The second number, $b$, must be smaller than this; it must also be smaller than $a$ itself, and furthermore it must be small enough that $c$ can possibly be on the list, that is to say $b < x-a-\min(pile)$. The second number must also be larger than half of these leftovers so it's larger than whatever $c$ ends up being, which means $\frac{x-a}{2} < b < \min(a,x-a-\min(pile))$, that is, $12\,012.5\le b < 12\,578$. There are actually no candidates for $b$ that work for this $a$! The first one that meets these requirements is $a=33\,749$ and $b=18\,905$.
Finally, we don't need to try values for $c$; we can simply calculate $c=x-a-b$ and see if that's in the list. From $120$ things to check we've gone down to just $9$, and the answer is $33\,749+18\,686+12\,797=65\,232$.
Similar work will do the job very quickly for the other two values: there are $9$ candidates for $73\,002$ and only $6$ for $56\,273$.
We can generalize this:
To find a subset of size $n$ in a set $S$ of non-negative numbers that adds to a value $x$:
Then $a_k$, the $k$th highest value, must be at least $\frac{\sum_{j=1}^{k-1}a_j}{n-k-1}$, and at most the minimum of $a_{k-1}$ and $x - \sum_{j=1}^{n-k}S_j$, where $S$ is in order from lowest to highest. Iterate, depth-first, available values for $a_k$; upon reaching $a_n$ the above bounds converge on a single value, and if that's in $S$ then you win.
