An interesting programming challenge

[Colin Holgate]

Don’t you have to continue exploring, if the running total goes over 31? There may be a mixture of negative and positive numbers ahead, that will show up a different valid slice of numbers.

I tried using Jerry’s approach under ActionScript, slightly modified to use arrays instead of strings, and it took just over 300 mS. Tried as Javascript too, and that seemed to be under 2 milliseconds!

> On Apr 10, 2015, at 10:36 AM, Ben Rubinstein <benr_mc at cogapp.com> wrote:
> 
> I think the thing is that you can do recursion either depth-first or breadth-first.  Because we don't need to build up all the combinations (or even all the sums), but just test them as we go; and because some combinations never need to be explored (because they go over the desired sum before all the numbers have been added); if you do it depth-first, it doesn't use very much memory at all.