An interesting programming challenge

[Ben Rubinstein]

On 10/04/2015 15:48, Geoff Canyon wrote:
> One thing that occurred to me about brute-forcing it: the sum of the entire
> list is 129,161,818. If there is a set that adds up to 100,000,000, then
> that means that the rest of the numbers have to add up to 129,161,818 -
>   100,000,000 = 29,161,818. So to make the brute force consider fewer
> options/be quicker, you could search for sets that add up to 29,161,818 and
> bail out whenever your total goes over that number instead of 100,000,000.
> Once you find such a set, take the numbers*not*  in that set, and you're
> done.

Ooooh, that _is_ clever!

Simply calling my function with a target of 29,161,818 finds all solutions 
(there's only one, of course) in about 2 seconds after I removed the alert 
when it's found, versus 160 seconds with a target of 100,000,000.

There must be a general version of this pattern - where there's an inverse of 
the answer you're looking for, which implies the desired answer but is easier 
to calculate.

Very nice.

Ben