> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/shu-xue/282-gei-biao-da-shi-tian-jia-yun-suan-fu.md).

# \[282]\[困难]\[回溯] 给表达式添加运算符

## 题目描述

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

示例 1:

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

示例 2:

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

示例 3:

```
输入: num = "105", target = 5
输出: ["1*0+5","10-5"]
```

示例 4:

```
输入: num = "00", target = 0
输出: ["0+0", "0-0", "0*0"]
```

示例 5:

```
输入: num = "3456237490", target = 9191
输出: []
```

提示：

* 0 <= num.length <= 10
* num 仅含数字

## 解题思路

容易想到本题解法的基本形式, 是按顺序遍历一个个数字, 然后尝试`+, -, *`的任意一种, 计算结果, 继续向下寻找数字. 因此需要使用DFS进行递归搜索.

首先在遍历确定数字时, 如果得到的数字是运算符前面的数字, 在DFS递归时就需要依次带着三种运算符进入到下一层, 而如果当前选择的符号是加减号, 而之后紧邻的一个运算符是乘号, 下次的递归就可以影响本次递归, 从而发散.

与计算器的题目[\[227\]\[中等\]\[栈\] 基本计算器 II](https://github.com/garnetow/garnetbook/tree/3585ab5a8f3ad10647527a472d38c58a23c60c4e/Algorithm/栈/227-基本计算器-II.md)类似, 由于`*`的存在, 运算符存在优先级, 我们确定的数字, 其实是在确定运算符后面的数字. 因为确定完运算符后面的数字之后, 就可以对最后的运算符遍历穷举计算了, 并且时刻记录着前一个数字, 在遇到乘号时, 也能够方便的**回溯**, 重新计算更正当前结果.

具体来说, 在递归时, 我们需要维护几个变量:

* `current_index`: 当前数字的起始位置
* `current_res`: 当前表达式计算结果
* `path`: 当前表达式
* `pre_num`: 前一个数字

path与current\_res是对应的. 在寻找新的数字时, 遍历从`current_index`开始一直遍历到原数字字符串的最后一个字符, 确定下新的数字后, 就可以枚举三种运算符, 与之前已经生成的表达式path结合, 更新结果current\_res, 并得到新的path. 三种运算符对应着三种情况:

* `+`: 直接与之前的表达式结合, current\_res直接加上当前数字得到新表达式的值
* `-`: 直接与之前的表达式结合, current\_res直接减掉当前数字得到新表达式的值
* `*`: 由于乘法的优先级更高, 之前最后一个数字pre\_num需要优先与当前产生的新数字计算, 而之前表达式current\_res中已经包含了pre\_num, 因此current\_res需要先抵消掉pre\_num, 然后再加上pre\_num与当前数字相乘的结果, 作为新的current\_res. 这里用了**回溯**的思路

因此前一个数字pre\_num的更新起着至关重要的作用. 枚举三种可能的运算符, 计算得到新的表达式结果之后, 需要准备下一步递归, 当前数字也就成了下一步运算的pre\_num. pre\_num的更新也于当前步选择的运算符有关. 记当前数字为`new_num`:

* `+`: `pre_num`更新为`new_num`
* `-`: `pre_num`更新为`-new_num`
* `*`: 上面计算的过程可以看到只有遇到`*`时才会使用`pre_num`, 如果下一个运算符还是`*`, 由于本次计算也是乘法, 相当于连乘, 因此下一个运算符`*`对应的下一个数字的`pre_num`, 需要更新为当前乘法运算子表达式的结果, 即`pre_num*new_num`

经过上面的转换, 乘法运算就可以直接将当前数字new\_num与pre\_num相乘, 而无需再考虑pre\_num之前的运算符了. 这个技巧在[\[227\]\[中等\]\[栈\] 基本计算器 II](https://github.com/garnetow/garnetbook/tree/3585ab5a8f3ad10647527a472d38c58a23c60c4e/Algorithm/栈/227-基本计算器-II.md)也是有体现的.

另外需要注意以下几点:

* 由于始终是在确定运算符的后一个数字, 而在开始时, 需要确定第一个数字, 这里需要区别对待下, 在current\_index为0时, 就是在寻找第一个数字. 因此只需更新当前表达式和pre\_num即可, 无需枚举它之前的运算符
* 如果枚举的数字长度大于1, 且以`0`开头, 这种情况于单独地把这个`0`拿出, 然后再继续枚举的情况相同, 因此可以**剪枝**
* 当寻找数字的起始位置current\_index超过原数字字符串长度时, 说明已经遍历完毕, 得到了一个表达式, 就可以判断结果是否与目标target相等了

```python
class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        n = len(num)
        res = []
        if not n:
            return res

        def dfs(current_index, current_res, path, pre_num):
            """
            Args:
              current_index: 当前数字起始索引
              current_res: 当前表达式计算结果
              path: 当前表达式
              pre_num: 前一个数字
            """
            if current_index == n:
                if current_res == target:
                    res.append(path)
                return

            for i in range(current_index, n):
                if num[current_index] == '0' and i != current_index:  # 剪枝
                    break

                new_num = num[current_index: i + 1]
                int_num = int(new_num)
                if current_index == 0:  # 确定第一个数
                    dfs(i + 1, int_num, path + new_num, int_num)
                else:
                    dfs(i + 1, current_res + int_num, path + '+' + new_num, int_num)
                    dfs(i + 1, current_res - int_num, path + '-' + new_num, -int_num)
                    dfs(i + 1, current_res - pre_num + pre_num * int_num, path + '*' + new_num, pre_num * int_num)

        dfs(0, 0, '', 0)
        return res
```