Hey /r/learnprogramming,

I'm practising for the spanish computer olympiads. In doing so I stumbled upon a problem in which I think a Depth-First search would work great.

For those of you who know spanish, the problem PDF is here: http://cl.ly/NoCy

Basically, I need to check if I can get the number n by adding or subtracting a vector of numbers I'm given. For example, with the numbers [1, 2, 3, 4, 5, 6, 7] you can get the number -2 by doing 1 2 3-4-5-6 7 = -2.

So, my approach is to check all the possible permutations of the signs by traversing a tree that looks like this: http://cl.ly/NnjY

I can get the 60% of the problem using this code: http://paste.pm/5m2.cpp

However, for large input vectors my program takes a lot of time. This is where I'd need help optimising my implementation.

I think I could "cache" chunks of the trees, but I'm not sure how I'd decide which branches to cache and how to uniquely identify them.

Any help would be appreciated!