Given 4 numbers generate all the combinations using basic operators (+, -, *,/ and parentheses)such that the result is 24

Question

Given a list of 4 integers, I have to find out all the combinations of them using basic math operators and parentheses such that it evaluates to 24. For example if the 4 numbers are 1,2,3,4 the expressions 1*2*3*4 or (4+2)*(3+1) can evaluate to 24. I found the algorithm here but I don't fully understand it to implement the program.

Simple recursion can give me the combinations which don't include parentheses. I want to understand how to solve it where parentheses are involved.

Answer 1

To handle the 'parenthesis-problem' you could think of your problem as follows:

"Create all Binary Expression Trees containing the operators + - * / and the given numbers 1,2,3,4. The evaluated expression must be 24."

The parenthesis result from the evaluation-order implicit represented in the tree.

So simply create all possible trees, evaluate them to check if the result is 24 and than print the valid ones including the parenthesis (either by putting parenthesis around every operation, or only if evaluation-order needs them)