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

Question

这是在面试中问我的，

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 时递归终止。

这让我想知道是否有更好、更完善的解决方案。对此有什么想法吗？我在考虑表达式树的某种逆向构造。

Answer 1

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

1. 除以数字时，数字是否保持整数，1/5 是 float 、0 还是大的小数
2. 如果输入中只有一个，数字和运算符是否可以重复，如果是这样，如果找不到解决方案，似乎没有办法终止
3. 你可以使用括号还是输入可以有括号
4. 可以是负数吗
5. 你可以只打印 true 或 false 还是你必须找到一个有效的解决方案

我从这些问题中注意到的一件事是，如果除法是通过舍入进行的，并且运算符列表中有 + 和 /，那么您始终可以除法直到舍入到 1 然后添加。此外，如果您可以重复，乘法本质上是无关紧要的，因为它可以被许多加法代替。

我确信您的面试官希望您提出更多澄清问题的原因是，即使是我想到的一小部分问题也会在很大程度上改变问题。

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