math - Writing an algorithm to decide whether a target number can be reached with a set of other numbers and specific operators?

Question

I'm trying to learn more about algorithm design, and I've set myself the challenge of creating a simple game that presents users with an array of numbers, a target number, and a range of operators (plus, minus, multiply, divide, perhaps square root and such later). What I need to do is decide whether or not it's possible to make that target number using the available numbers in the array.

I'm a little stumped on where to begin with this. In different rounds of the game, different operators may be available, such as +, -, *, and /, + and -, only + and *, or all except +, etc.

Am I right in saying that I would effectively need a separate algorithm for each combination of operators (however many there are, 20 or whatever)? And if so, will I then need to iterate through each number in the grid, performing each available operator on each other number in the array? That seems overly messy, but I'm not really sure what other options there are. This option also doesn't follow any specific path through multiple operations (for instance if I wanted to make 7, I may do 12 + 5 - 10 if those were the only numbers available to me in the array).

Could anyone give me some pointers on where to begin with this kind of problem?

Answer 1

You are facing a more generalized problem of the Partition Problem, which is NP-Complete.

The Partition Problem is: Given n numbers, split them into two (distinct) groups A and B such that sum(A) = sum(B). Now, it is easy to see that if you have a problem with +,- operators and target number 0 - this is basically the same problem, and there is an immidiate reduction from Partition Problem to your problem.

From this we can conclude your problem is NP-Hard as well, and there is no known polynomial solution for your problem.

Alternatives are:

1. Brute Force (As suggested by @Sayakiss)
2. Depending on the operators - you might be able to use some branch and bound techniques.
3. For Partition Problem there is pseudo-polynomial Dynamic Programming solution, that might be utilized in here as well, at least for some of the cases.

Sorry if it's bad news -but at least you won't be looking for something that (most computer scientists believe) is not there