思路

Expression Add Operators，这是一道 hard 难度的题目，需要我们对给定的数字字符串num分为若干个连续子串，输出用 +、- 和 * 连起来后，等于target的表达式。这个题目解法全是暴力，没有一丝技巧。num的长度即为$n$，在两个数字之间可以选择进行四种操作（不插入符号、+、- 和 * ）。

如果不是会超时的话，大概直接 DFS 遍历四种操作，最后eval出结果就好了。考虑到这个问题尝试用eval来计算表达式结果超时的问题，我们需要在遍历过程中去计算表达式的结果。

下面的方法思路是在遍历过程中考虑数字如何划分，也就是说，每次加入表达式的数字是多少位，然后枚举 +、- 和 * 三种情况。

计算的话，如果是 + 或者 - 直接在先前结果上面加减即可。如果是 *，则需要把表达式最后一个单项式减去，再乘上新的数字，然后加回表达式之中。

也就是说，我们的递归函数dfs需要四个状态：exp记录已生成的表达式，index记录这次调用起始的num下标，res即已生成表达式的结果，preNum是最后一个单项式。

复杂度

时间复杂度: $O(4^n)$，$n$是num的长度，由于每个位置之间存在四种插入决策（不插入符号、+、- 和 *），共有$n−1$个位置可以插入符号，组成表达式需要$O(4^{n-1})$的复杂度，加上计算表达式需要$O(n)$复杂度，时间复杂度为$O(n4^{n-1})$…吗？根据这个题解（详见给表达式添加运算符），表达式的个数不会超过$O(3^{n-1})$，复制表达式到答案用时不超过$O(n3^{n-1})$。

空间复杂度: $O(n)$，递归栈空间和记录表达式的遍历空间复杂度都是$O(n)$，不考虑结果所占空间。

Code

ts
function addOperators(num: string, target: number): string[] {
    const ans = []
    const exp = []
    const numLen = num.length
    const dfs = (index: number, res: number, preNum: number) => {
        if (index === numLen) {
            if (res === target) {
                ans.push(exp.join(''))
            }
        } else {
            let curNum = 0
            const preLength = exp.length
            exp.push('')
            const signIndex = exp.length - 1
            for (let j = index; j < numLen; j++) {
                if (j !== index && num[index] === '0') {
                    break
                }
                curNum = curNum * 10 + (num[j] as any - 0)
                exp.push(num[j])
                if (index === 0) {
                    dfs(j + 1, curNum, curNum)
                } else {
                    exp[signIndex] = '+'
                    dfs(j + 1, res + curNum, curNum)
                    exp[signIndex] = '-'
                    dfs(j + 1, res - curNum, -curNum)
                    exp[signIndex] = '*'
                    dfs(j + 1, res - preNum + preNum * curNum, preNum * curNum)
                }
            }
            exp.length = preLength
        }
    }
    dfs(0, 0, 0)
    return ans
};