生成一个计算给定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 是否为浮点数、0 或大数小数
2. 如果输入中只有一个数字和运算符是否可以重复，如果是这样，如果找不到解决方案，似乎无法终止
3. 你可以使用括号或者输入可以有括号
4. 数字可以为负数吗
5. 你可以只打印 true 或 false 还是你必须找到一个有效的解决方案

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

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

最后要考虑的一件事是，这个问题是背包问题的超集，已知背包问题是 np 完全的，因此显然不存在多项式时间解。