algorithm - 分解字符串以形成有效的表达式

Question

我得到一个字符串 S(整数)和一个数字 N。我想在 S 中插入任意数量的“+”，以便总和等于 N。

Ex:<br>
S = 15112 and N = 28<br>
Ans is : 15+11+2<br>
S = 120012 and N = 33<br>
Ans is : 1+20+012<br>
S = 123 and N = 123<br>
Ans is : 123

给定:|S| <= 120 且 N <= 10^6
保证 S 和 N 总是可以形成有效的表达式。有什么算法可以解决这个问题吗？我试图思考这个问题，但无法想出解决方案。

Answer 1

可能有更有效的方法来做到这一点，但由于到目前为止你什么都没有......

您可以简单地找到一个 bool 数组的所有组合，该数组指示数字之间是否应存在加号。

例如:输入112134，1 + 12 + 13 + 4可以用 bool 数组[true, false, true, false, true] 表示第1、3、5个数字后面有一个加号。然后问题就减少到找到哪些组合可以添加到您的数字中。有很多方法可以找到组合。递归回溯是一个经典。

在 javascript/node 中，这可能看起来像这样:

function splitOnIndexes(arr, a) {
  // split the array into numbers based on the booleans
  let current = "" + arr[0]
  let output = []
  for (let i = 0; i < a.length; i++) {
    if (!a[i]) {
      current += arr[i + 1]
    } else {
      output.push(current)
      current = "" + arr[i + 1]
    }
  }
  output.push(current)
  return output
}

function findSum(input, total) {
  function backtrack(n, k = 0, a = []) {
    const sum = (arr) => arr.reduce((a, c) => a + parseInt(c), 0)
    if (k === n) {
      let ans = splitOnIndexes(input, a)
      if (sum(ans) === total) {
        console.log(ans.join(' + '))
      }
    } else {
      k = k + 1
      let c = [true, false]
      for (let i = 0; i < 2; i++) {
        a[k - 1] = c[i]
        backtrack(n, k, a)
      }
    }
  }

  backtrack(input.length - 1)
}

findSum('15112', 28)

findSum('120012', 33)

findSum('123', 123)

如您所见，可能有多个答案。你的第一个例子是用 15+1+12 和 15+11+2 解决的。如果你只需要一个，你当然可以提前停止。