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.

Damarisdamarra

Is 1 and + always present in the input? Does the output must be the shortest? Otherwise you could always return 1+1+1+1+1...+1 = n. – Tollhouse

Not necessarily, its just an example – Damarisdamarra

So, can you need a number multiple times although it occurs in the input only once? Also, do you have to use all the input numbers? – Carisacarissa

Yes, you can use the number/operator multiple times, No, you dont have to use all input numbers – Damarisdamarra

Is there some restriction on the input number range? I ask because you are pretty much screwed if you get for example two large primes as an input. Also, is / integer division? – Carisacarissa

For what it's worth, I'm pretty sure the interviewer wanted you to write some semi-efficient backtracking solution here. I mean the problem is most definitely NP-hard and I can't see how you would design a pseudopolynomial DP algorithm – Carisacarissa

@NiklasB. I agree with you, probably the interviewer wanted him to try to demonstrate the problem was NP (or at least, try it). – Tollhouse

@Paulo: I'm still wondering whether there might be some O(P(max input number * input size)) pseudopolynomial algorithm where P is a polynomial. That would be much better than a exponential backtracking algorithm – Carisacarissa

I'm not even fully sure the problem is solvable for the general case the way you described it. If you can use operators and numbers repeatedly I don't see a way to decide when to terminate, going over the input is not valid because of division and subtraction, at least if you can't repeat operators and numbers the possibilities are finite and you have chances to reduce the runtime – Eskill

@aaronman: One common thing is to try and do it with 1 operators. If that doesn't work, try it with 2 etc. You can easily backtrack with pruning if you have set yourself an upper bound. That the problem is NP-complete doesn't mean its hard to solve under certain given restrictions, for example if the input numbers are bounded. – Carisacarissa

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.

Eskill

If the problem was reduced to using every number in the set only once, does that help? – Damarisdamarra

@Damarisdamarra everything helps, that was the point of my answer. IT thats what the interviewer was looking for. I'd have to have all my questions answered to propose a working solution – Eskill

here's what I'm thinking. 1) the division has to be exact. We cannot do a 1/5. A 4/2 yes. 2) The numbers dont repeat, the operators can 3) parenthesis should be allowable, it would be hard to form expressions without them 4) No negative numbers 5) valid solution needed – Damarisdamarra

one more to the list: when you do the calculations, do you use operator precendence? – Felixfeliza

@Damarisdamarra ah but if there r no negatives what happens to the - operators that go below 0 – Eskill

@aaronman: I assume the input numbers cannot be, put partial results can be. – Felixfeliza

@aaronman, the actual numbers aren't negative, but results could be? – Damarisdamarra

@KarolyHorvath, operator precedence should work, parenthesis are allowed as well – Damarisdamarra

@aaronman, ok, one thing though, how would you solve the most dumbed down version of the question? I'm looking for a suitable data structure to work with – Damarisdamarra

@Damarisdamarra the most dumbed down version of the problem is the knapsack problem, which is easily searchable on google – Eskill

@aaronman: Don't think there is a pseudopolynomial DP solution though, like there is for Knapsack. Backtracking is the way to go here, but we can do lots of pruning. – Carisacarissa

@NiklasB. my point is that if I was in this interview I would be asking clarifying questions about the problem till the end of time because at it's most general it might be unsolvable and at it's most narrowed down it's trivial (and in the middle it's just the knapsack problem ;) – Eskill

@aaronman: Yep, agreed. I, too, think that interviewer wanted to hear more about the interviewee's thoughts than to get a bad implementation. – Carisacarissa

@NiklasB. correct me if I'm wrong but if there are literally no restrictions, I feel like the problem might actually be unsolvable, like asking the solution to the halting problem in an interview – Eskill

@aaronman: My intuition says it's decidable because with some cleverness and dependent on the input you might be able to determine an upper bound to the number of necessary operators, but that seems to be far from trivial to prove. – Carisacarissa