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?
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:
Sorry if it's bad news -but at least you won't be looking for something that (most computer scientists believe) is not there
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With