algorithm - 添加 +/- 以生成以 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 图，您只需搜索它即可找到解决方案。简单的广度优先搜索或深度优先搜索都可以，但我认为如果解空间很大，速度会很慢。

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