Writing an algorithm to determine if a target number can be achieved using a set of other numbers and specific operators?

Question

I am trying to learn more about the design of algorithms, and I set myself the task of creating a simple game that presents users with an array of numbers, a target number and a series of operators (plus, minus, multiply, divide, possibly the square root, and so on). I need to decide if this target number can be made using the available numbers in the array.

I am a little puzzled where to start. Different operators may be available in different rounds of the game, such as +, -, *, and / , + and - , only + and * or all but + , etc.

Am I right in saying that I really need a separate algorithm for each combination of operators (be that as it may, 20 or something else)? And if so, then I will need to go through each number in the grid, executing each available operator from each other in the array? This seems too confusing, but I'm not quite sure what other options exist. This option also does not correspond to a specific path through several operations (for example, if I wanted to do 7 , I can do 12 + 5 - 10 if they were the only numbers available to me in the array).

Can someone give me some guidance on where to start this problem?

Answer 1

You are facing a more general issue of the partition problem , which is NP-Complete .

Section objective: considering the numbers n , divide them into two (separate) groups A and B such that sum(A) = sum(B) . Now it's easy to see that if you have a problem with the +, - operators and target number 0 - this is basically the same problem, and you have a problem with the partition problem in your problem.

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

Alternatives:

• Brute force (as suggested by @Sayakiss)
• Depending on the operators, you can use some industry and related methods .
• For the partition problem, there is a pseudo-polynomial solution for dynamic programming , which can be used here, at least for some cases.

Sorry if this is bad news, but at least you will not be looking for something that (according to most computer scientists) does not exist

Answer 2

• List all possible expressions. For numbers 1,2,3 and operator + and - you can get: 1 + 2 + 3.1 + 2-3.1-2 + 3.1-2-3.

• Evaluate all possible expressions.

Answer 3

Here is the Java solution from programcreek.

 public static boolean isReachable(ArrayList<Integer> list, int target) { if (list == null || list.size() == 0) return false; int i = 0; int j = list.size() - 1; ArrayList<Integer> results = getResults(list, i, j, target); for (int num : results) { if (num == target) { return true; } } return false; } public static ArrayList<Integer> getResults(ArrayList<Integer> list, int left, int right, int target) { ArrayList<Integer> result = new ArrayList<Integer>(); if (left > right) { return result; } else if (left == right) { result.add(list.get(left)); return result; } for (int i = left; i < right; i++) { ArrayList<Integer> result1 = getResults(list, left, i, target); ArrayList<Integer> result2 = getResults(list, i + 1, right, target); for (int x : result1) { for (int y : result2) { result.add(x + y); result.add(x - y); result.add(x * y); if (y != 0) result.add(x / y); } } } return result; }