Coincidentally I was just solving (a variant of) this problem today. The approach I took is taking the list of numbers and recursively replacing each pair (x, y) with x+y (replace + with any operation), until one element remains.
You can separate the process by transforming the list of numbers into a binary tree and applying the operators at the nodes. You then consider all possible binary trees and all combinations of operators.
Bonus: by sorting the input values, you can consider half of the trees, because the operations either commute (x+y = y+x) or don't make sense to reverse in the integers (4/2 vs. 2/4).
(Author here) Oh that's pretty clever and better than my approach. I was going to point out that subtraction would still need to be supported but realized we don't need to support negative numbers.
There is a similar game that is available for Android and iOS called Calculords (http://calculords.com/)
The goal is to apply arithmetic operations on a set of numbers in order to get outputs which correspond to your available attacks. It is not as strict as Num, where only one output is expected.
Some friends and I were hooked on this game in college. We eventually wrote a program to solve particularly tough hands. It turns out there are a few potential hands that are actually impossible to solve, but not very many! It's a fun programming problem. :-)
1) 39+525+7-8 also works if I understand the problem.
2) You can optimize using various number-theoretic principles -- checked division and subtraction
3) C++ is much much faster for this -- less than a second on my boxes.
Not sure where people get the idea of dynamic programming -- you can do some dynamic tree cutting (e.g. if you don't have enough operators to get to your target), but there's no real objective function here.
My machine finished the original implementation in:
07:53
I then tried skipping the set of operators and just doing list lookups (figuring the set overhead defeats the advantage when the collection is so small):
08:24
My next idea was to replace the set lookup with an isinstance() check:
09:01
My third proposed change is the only one that has given me a speed-up:
You can separate the process by transforming the list of numbers into a binary tree and applying the operators at the nodes. You then consider all possible binary trees and all combinations of operators.
Bonus: by sorting the input values, you can consider half of the trees, because the operations either commute (x+y = y+x) or don't make sense to reverse in the integers (4/2 vs. 2/4).