# 题目: 282. 给表达式添加运算符

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ,在 num 的数字之间添加 二元 运算符(不是一元)+- 或 * ,返回所有能够得到目标值的表达式。

# 示例1:

输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"] 

# 示例2:

输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]

# 题解: 回溯模拟

根据题目,在目标字符串 num 中,每一个空隙随意的插入四个符号 *,-,+,''中的一个。

可以使用用「回溯法」来模拟这个过程。

从左向右构建表达式,并实时计算表达式的结果。由于乘法运算优先级高于加法和减法运算,我们还需要保存最后一个连乘串(如 234)的运算结果。

定义一个递归函数用于回溯:

  • expr 为当前构建的表达式
  • i 表示当前枚举到的字符串的第 i 个数字
  • res 为当前表达式计算的结果
  • mul 为表达式最后一个连乘串的计算结果。

关于递归函数的终止

  • i === n 的时候,表明字符串已经构建完毕,此时以 res === target 为判断构建字符串是否符合标准
  • i < n 的时候,对字符串添加一个操作符
    • 若 添加 + 号
    • 若 添加 - 号
    • 如 添加 * 号

# 参考资料