algorithm - 如何仅使用加法和减法从整数序列中获取整数

Question

例如，给定一个像 4、10、4、7 这样的序列，我们需要得到 10。答案是 4+10-4=10。建议使用什么样的方法。我可以用DP解决它吗？谢谢！

Answer 1

我想到的最接近动态编程算法的是以下（Python）：

def find_number(numbers, goal):
    # sum 0 can be reached with empty sequence
    found = {0: []}
    # iterate over all numbers in the list
    for n in numbers:
        # update dict of found numbers with m+n and m-n for each m in found
        found = dict([(m + n, path + [+n]) for (m, path) in found.items()] +
                     [(m - n, path + [-n]) for (m, path) in found.items()])
        # check whether the goal number is among them
        if goal in found:
            return found[goal]

除了递归树遍历算法之外，这可能具有防止一些双重工作的优点，因为中间结果（可以达到序列中某个数字的数字）存储在哈希映射中。（也就是说，如果使用第一个数字的多个组合可以达到某个k数字，则只有其中一个存储在地图中。）可以通过消除即使添加或减去也可能无法达到目标的中间结果来进行进一步优化所有剩余数字的总和。

尽管如此，就像递归方法一样，最坏情况的复杂性（时间和空间）甚至可能是平均情况的复杂性仍然是列表长度的指数，因为found映射的大小在每次迭代中都可以翻倍。

Answer 2

这是 JavaScript 中的一个示例。如果需要，您可以更改序列中的数字。只有在匹配时才会记录结果。

var sequence = [4, 10, 4, 7],
    tree = []

for (var i=0; i<sequence.length; i++){
  tree.push([sequence[i], -sequence[i]])
}

function findMatch(arr, match, numSoFar, path, iterations){
  var numSofar1 = numSoFar + arr[iterations][0],
      numSofar2 = numSoFar + arr[iterations][1],
      path1 = path + (arr[iterations][0] > 0 && iterations > 0 ? "+" : "") 
              + String(arr[iterations][0]),
      path2 = path + (arr[iterations][1] > 0 && iterations > 0 ? "+" : "") 
              + String(arr[iterations][1])

  if (numSofar1 == match) console.log(path1)
  else if (numSofar2 == match) console.log(path2)
  else if (iterations < arr.length-1){
    findMatch(arr, match, numSofar1, path1, iterations + 1)
    findMatch(arr, match, numSofar2, path2, iterations + 1)
  }
}

findMatch(tree, 10, 0, "", 0)