生成计算给定N的有效表达式

这是在面试中问我的，

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.

现在，我的解决方案是一个蛮力的递归解决方案，它贯穿所有可能的数字和所有可能的操作，当数字超过N或等于N时，递归终止。

这让我想知道是否有更好的，更精致的解决方案。 对此有何想法？ 我正在考虑某种表达树的逆向构造。

---

我会继续说，这个面试问题不仅仅是试图通过提问来缩小问题的范围。 有一个非常大的问题列表，你没有涉及的问题可能对解决方案很重要，因为

数字在分割时是否保持整数，所以1/5是浮点数，0或者是小数

如果只有一个在输入中，数字和运算符是否可以重复？如果没有找到解决方案，似乎无法终止

你可以使用括号还是输入可以使用括号

这些数字可能是负数

你可以打印真假还是必须找到有效的解决方案？

从我注意到的这些问题中，有一件事是如果分割是通过四舍五入来实现的，并且在运算符列表中有一个+和/ ，则可以一直进行分割，直到它变为1，然后只是添加。 此外，如果你可以重复乘法基本上是无关的，因为它可以被许多补充。

我相信你的面试官希望你提出更多澄清问题的原因是因为即使是我认为的一小组问题也会以很大的方式改变这个问题。

最后要考虑的一件事是，这个问题是背包问题的一个超集，已知它是np完备的，所以显然没有多项式时间解。

链接地址: http://www.djcxy.com/p/77183.html

上一篇: Generate a valid expression that computes to given N

下一篇: Maximum number of elements in an array vs. maximum indexer value