Generate a valid expression that computes to given N

Question

This was asked to me in an interview,

Given a list of integer numbers, a list of symbols [+,-,*,/] and a target number N,  
provide an expression which evaluates to N or return False if that is not possible. 
e.g. let the list of numbers be [1,5,5] and the target number is 9, one possible 
solution could be 5+5-1.

Now, my solution was a brute-force recursive solution that runs through all possible numbers and all possible operations and the recursion terminated either when the number exceeded N or was equal to N.

This got me wondering if there was a better, more refined solution. Any thoughts on this? I was thinking some kind of reverse construction of an expression tree.

Answer 1

I'm gonna go ahead and say this interview question cannot be about anything more than trying to narrow the problem down by asking questions. There is an extremely large list of questions you haven't covered that could be important to the solution, for

1. Do the numbers stay integers when you divide them, so is 1/5 a float, 0 or a big decimal
2. Can the numbers and operators repeat if only one is in the input, if so there seems to be no way to terminate if you can't find a solution
3. can you use parentheses or can the input have parentheses
4. can the numbers be negative
5. can you just print true or false or do you have to find a valid solution

One thing from those questions I notice is that if division works by rounding and you have a + and / in the operator list, you can always divide until it rounds to 1 and then just add. Also if you can repeat multiplication is essentially irrelevant because it can be replaced by many additions.

The reason I am sure that your interviewer wanted you to ask more clarifying questions is because even the small set of questions that I thought of change the problem in a big way.

One last thing to consider, this problem is a superset of the knapsack problem which is already known to be np-complete, so there is obviously no polynomial time solution.