Hacker News Reader

That was fun, good waste of time while my code was compiling. I just used C++ and hacked up a prime seive for #2 and for #3 used a combination generator I had previously used before - http://photon.poly.edu/~hbr/boost/combinations.html

View on HN

for #3 used a combination generator

Congratulations, you just used an exponential-time algorithm for a polynomial-time problem.

Congratulations are in order, he sacrificed 400ms CPU time to save at least a few minutes of coding time.

I wasn't being entirely sarcastic. It never occurred to me that you could use a non-polynomial-time algorithm.

All the solutions posted here seem to involve generating all subsequences. Could you say more about your approach?

Not always is "exponential" a bad thing. For small sets, the expo algorithm is actually faster than the polynomial one. Although yeah, generally speaking, it's a bad idea.

I tried on #3 the most inefficient algorithm I could come up with - blindly going through all possible combinations and checking if their biggest member is equal to the sum of the rest. Time of the execution: 0.6s

I am not sure if this step of allowing the "shortcuts" was part of the game or not. All that would had to be done is to give 128 elements of the array to exclude at least the most blatant brute-forcing.

Reply on news.ycombinator.com