1

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

例如，

123 => 1 + 2 -3 = 0

173956 => 17 + 39 - 56 = 0

除了蛮力方法之外，我没有解决这个问题的线索。

有什么建议吗？

4

2 回答 2

1

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

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

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

于 2012-10-18T06:22:27.673 回答
0

您可以通过多种方式解决它，例如使用递归方法，如果您将其构建为树，这将变得很明显

例如 123

因为一个数字后可以有两个不同的符号(+|-) ：

        1
       / \
      +   -
     /     \
    2       2   
   / \     / \
  +   -   +   -
  |   |   |   |
  3   3   3   3
于 2012-10-18T06:21:51.460 回答