添加+/-以使数值字符串的计算结果为0

Question

给定一个由数字组成的字符串，添加+或-号以使表达式值为0。返回表达式。

例如,

123 => 1+2 -3 =0

173956 => 17 + 39 - 56 =0

除了暴力破解之外，我没有任何线索来解决这个问题。

有什么建议吗？

Answer 1

这是一个搜索问题。搜索必须在解空间中执行。假设我们从'123‘字符串开始，此时，我们可以在'1’后面加上+或-号，结果我们得到了'1 + 23‘或'1 - 23’。每个变体都可以通过在下一个字符后面添加一个符号来进一步拆分。因此，所有可能的符号加法都将形成树状结构--解空间。您的算法必须在此结构中搜索解决方案。我认为A*可以用来做这件事。

Anders K绘制了很好的解空间的ASCII图，你只需要搜索它的解。简单的广度优先搜索或深度优先搜索可以完成这项工作，但如果解空间很大，我认为它会很慢。

此外，我认为有可能找到更优化，更具体的解决方案，利用解决方案空间的属性，例如-它的树状结构。

Answer 2

你可以用很多方法来解决它，例如，使用递归方法，如果你把它构造成一个树，这一点就会变得很明显

例如123

由于数字(+|-)后面可能有两个不同的符号：

        1
       / \
      +   -
     /     \
    2       2   
   / \     / \
  +   -   +   -
  |   |   |   |
  3   3   3   3