Given a set of numbers (in this case):
3, 7, 7, 100, 50
prove it is impossible to form the number k = 190 using ( ) + - * / operators between sub set of the these numbers ex: 1000 = ((3 + 7) * 100)
find the expression that does form the number k = 190.
I am not sure how to work on this problem analytically as the general case of any subset and any number k appears to be an NP Hard problem.
I wish to brute force the solution for this. Is the following algorithm sufficient:
Take set F: Compute all possible ordered subsets of F (How to do this elegantly?)
Compute all possible combinations of operators between each ordered subset...
If any equal 190 then the problem is solved, if none equal 190 then clearly its not possible.
How do I generally design this algorithm? Is there a better way to solve this problem (preferably without brute force)?
My attempt at analytics:
I wanted to see if by working with the number modulo Q it would be easy to filter out which possible expressions may evaluate to 190. Since the expression S = 190 must be true mod Q for all Q if it is true.
My other attempt at brute force:
Starting from 190, systematically, add, subtract, divide, etc... expressions from the original set in the hope that one of these expressional chains concludes in a value that is still present in the set. This seems to be as computationally expensive as the previous method (How would I implement this?)