表达式添加运算符如何用回溯？乘法优先级为什么要记录 last？

简化版

表达式添加运算符是在数字字符串中插入 +、-、*，让表达式结果等于目标值。

回溯时枚举下一段数字，以及它前面放哪个运算符。

为了处理乘法优先级，需要记录当前表达式值 value 和上一段参与加减的值 last；遇到乘法时用 value - last + last * cur 修正结果。

详细版

递归状态包括：

当前处理到字符串下标 index；
当前表达式字符串 expr；
当前表达式计算值 value；
最近一次加到结果里的项 last。

如果选择 +cur，新值是 value + cur，last = cur。

如果选择 -cur，新值是 value - cur，last = -cur。

如果选择 *cur，要把之前的 last 从结果里撤掉，替换成 last * cur，所以新值是 value - last + last * cur。

前导零也要处理：片段 "0" 合法，"05" 不合法。

完整版教学

一、为什么这题不是简单字符串枚举

题目确实要枚举所有插入运算符的可能，但难点在于边枚举边计算表达式值。加法和减法可以直接更新结果，乘法有更高优先级，不能简单地 value * cur。如果每次都生成完整表达式再用解释器计算，会成本高且面试里不允许依赖 eval。

记忆钩子：表达式回溯的核心不是插符号，而是实时维护计算值。

二、为什么需要 last

考虑表达式 1 + 2 * 3。当我们已经得到 1 + 2 时，value = 3，last = 2。接下来遇到 *3，真实结果应该是 1 + (2*3) = 7，不是 (1+2)*3 = 9。所以要从 value 中撤销上一个项 2，再加上 2*3。

newValue = value - last + last * cur

如果上一个操作是减法，例如 1 - 2 * 3，last = -2，公式仍然成立：1 - (-2) + (-2)*3 = -5。

三、递归状态表

状态	含义	示例
`index`	处理到数字字符串哪里	3
`expr`	当前表达式	`1+2`
`value`	当前表达式值	3
`last`	最近一个可被乘法合并的项	2

这四个状态能同时描述搜索位置、输出路径和计算结果。

四、代码模板

实现如下：

function addOperators(num, target) {
  const ans = []

  function dfs(index, expr, value, last) {
    if (index === num.length) {
      if (value === target) ans.push(expr)
      return
    }
    for (let end = index; end < num.length; end++) {
      if (num[index] === '0' && end > index) break
      const str = num.slice(index, end + 1)
      const cur = Number(str)
      if (index === 0) {
        dfs(end + 1, str, cur, cur)
      } else {
        dfs(end + 1, expr + '+' + str, value + cur, cur)
        dfs(end + 1, expr + '-' + str, value - cur, -cur)
        dfs(end + 1, expr + '*' + str, value - last + last * cur, last * cur)
      }
    }
  }

  dfs(0, '', 0, 0)
  return ans
}

第一段数字前面不能加运算符，所以要单独处理 index === 0。

五、带数字推演

num = "123"，目标 6。

1+2+3 = 6
1*2*3 = 6

当生成 1+2 后再接 *3，公式得到 value - last + last*cur = 3 - 2 + 6 = 7，对应 1+2*3，不会错误算成 9。

六、常见误区与追问

误区：乘法时直接 value * cur。 这会把整个表达式都拿去乘，破坏优先级。
误区：使用 eval。 面试题重点是搜索和计算状态，不能依赖解释器。
误区：允许前导零数字。 "05" 这类片段非法，会产生错误表达式。
追问：为什么 last 对减法要存负数？ 这样乘法修正公式可以统一处理 + 和 -。
追问：复杂度是多少？ 每个间隙可切分或放 3 种符号，搜索空间指数级，输出规模也可能很大。

这些点说明你是否真正处理了运算符优先级。

七、加强记忆

表达式添加运算符记成“枚举数字段，三种符号分支，乘法靠 last 修正”。value 保存当前结果，last 保存最近一个加减项；乘法时用 value-last+last*cur 替换上一项。第一段没有符号，前导零要剪掉。这个题的灵魂就是边回溯边正确算值。

简化版

详细版