Given something like this:
1 5 3 4 = 18
I need to determine (using an algorithm) if there is a combination of operators and brackets that bring me to 18. Only "+" and "*" and "(" and ")" are allowed.
Example:
1 + 5 + ( 3 * 4 ) = 18
Beside brute force, is there any particular algorithm that is able to compute all the possible combo in reasonable time? RPN may help in order to encode the possible solutions, but the same are a lot (4^n ?).
Best Answer
Brute force is actually quite fast if you avoid pointless calculations.
In the worst case you have 2^(N-1) operators and N!(N-1)! ways of choosing the pairs of numbers for the N-1 operations. So for example, for N=4, this gives 1,152 possibilities.
But you can cut this down substabtially: if you are going to look at 6+2 and 6*2, then there is no need to look at 2+6 and 2*6: just do the bigger number first. This takes out a factor of 2^(N-1) bringing the number of possibilities down to N!(N-1)!, so 144 for N=4.
There are further possible savings as (20+6)+2 is the same as 20+(6+2), but I suspect this may not be worth optimising for until N becomes large. Another is that multiplication by 1 does not help much: this kind of thing may not be a saving with N=4, but could be if you were also for example looking at division (especially if the smaller number is not a factor or divisor of the larger number) as you can then remove a bunch of possibilities. rzzzwilson's suggestion of stopping when the target is exceeded works in a similar way, though only works if the all the operations are non-decreasing (i.e addition and multiplication but not subtraction or division)
As an illustration of something similar, try my old Java applet here, with six numbers and four operators. You can put your own numbers and target in the box. It is not prettily programmed, but is still quite quick.