java - 查找整数字符串的排列(使用 + 和 -)是否与数字匹配

Question

基本上我正在做的事情是使用一个整数字符串(例如“1234”)，并且我可以在此字符串中的任何位置插入一个 + 或 - ，可以随意插入。例如，我可以做“1 + 2 + 3 + 4”，“12 + 34”，“123 - 4”等。要求使用字符串的所有整数，我不能排除任何一个。

我想做的是获取另一个整数数组，并找出是否可以使用第一段中提到的排列来获得该数字。我有点不知道从哪里开始寻找这个。我可能会创建一个递归循环函数来创建字符串的每个可能组合，并查看每个结果是否匹配，但这似乎非常慢。另一个想法是将它们索引到一个数组中 - 这样我就可以在计算一次之后简单地查找答案。

有人有什么建议吗？

Answer 1

I could possibly create a recursive loop function to create every possible combination of the string and see if each result matches but this seems like it will be terribly slow.

进行详尽的搜索是您唯一的选择。幸运的是，即使对于最多 7..10 个字符的中等长度字符串，时间也不会太糟糕，因为在处理“尾部”时不需要“重做”先前字符串的加法和减法。

可能的实现大纲如下:

1. 将整数数组中的所有所需结果放入哈希集中
2. 制作一个递归方法，获取到目前为止的结果、字符串和下一个“剪切”的位置
3. 当下一个“cut”位于字符串的末尾时，根据步骤 1 中的哈希集检查到目前为止的结果
4. 否则，在 k 上循环尝试这三种可能性
   • 使用“cut”中的 k 位数字作为正数，并使用移动 k 位的“cut”进行递归调用。这相当于在剪切处插入一个+
   • 使用“cut”中的 k 位数字作为负数，并使用移动 k 位的“cut”进行递归调用。这相当于在剪切处插入一个-