282. Expression Add Operators

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators ‘+’, ‘-‘, and/or ‘*’ between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

Input: num = “123”, target = 6
Output: [“1*2*3“,”1+2+3“]
Explanation: Both “1_2_3” and “1+2+3” evaluate to 6.

Example 2:

Input: num = “232”, target = 8
Output: [“2*3+2“,”2+3*2“]
Explanation: Both “2*3+2“ and “2+3*2“ evaluate to 8.

Example 3:

Input: num = “3456237490”, target = 9191
Output: []
Explanation: There are no expressions that can be created from “3456237490” to evaluate to 9191.

回溯思路

设字符串 的长度为 n，为构建表达式，我们可以往 中间的 个空隙添加 号、 号或 号，或者不添加符号。

我们可以用「回溯法」来模拟这个过程。从左向右构建表达式，并实时计算表达式的结果。由于乘法运算优先级高于加法和减法运算，我们还需要保存最后一个连乘串（如 ）的运算结果。

这里困难的是如何处理优先级运算。我们可以每次记录当前结果和最后计入() 的连乘串。这样万一下面还是号，则撤销上一步计算结果，重新加上的结果作为，从而达到直接按从左到右的顺序求出有乘法的表达式。

定义递归函数 #card=math&code=%5Ctextit%7Bbacktrack%7D%28%5Ctextit%7Bexpr%7D%2C%20i%2C%20%5Ctextit%7Bres%7D%2C%20%5Ctextit%7Bmul%7D%29&id=nhTgr)，其中：

• 为当前构建出的表达式；
• 表示当前的枚举到了 的第 $i $个数字；
• 为当前表达式的计算结果；
• 为表达式最后一个连乘串的计算结果。

该递归函数分为两种情况：

如果 ，说明表达式已经构造完成，若此时有 ，则找到了一个可行解，我们将 放入答案数组中，递归结束；

如果 ，需要枚举当前表达式末尾要添加的符号（ 号、 号或 号），以及该符号之后需要截取多少位数字。设该符号之后的数字为 ，按符号分类讨论：

• 若添加 号，则 增加 ，且 单独组成表达式最后一个连乘串；
• 若添加 号，则 减少 ，且 单独组成表达式最后一个连乘串；
• 若添加 号，由于乘法运算优先级高于加法和减法运算，我们需要对 撤销之前 的计算结果，并添加新的连乘结果 ，也就是将 减少 并增加。

代码实现时，为避免字符串拼接所带来的额外时间开销，我们采用字符数组的形式来构建表达式。此外，运算过程中可能会产生超过 32 位整数的结果，我们要用 64 位整数存储中间运算结果。

代码

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        int n = num.length();
        vector<string> ans;
        function<void(string&, int, long, long)> backtrack = [&](string &expr, int i, long res, long mul) {
            if (i == n) {
                if (res == target) {
                    ans.emplace_back(expr);
                }
                return;
            }
            int signIndex = expr.size();
            if (i > 0) { //刚开始不用占位！！
                expr.push_back('T'); // 占位符，下面填充具体符号
            }
            long val = 0;
            // 枚举截取的数字长度（取多少位），注意数字可以是单个 0 但不能有前导零
            for (int j = i; j < n && (j == i || num[i] != '0'); ++j) {
                val = val * 10 + num[j] - '0';
                expr.push_back(num[j]);
                if (i == 0) { // 表达式开头不能添加符号
                    backtrack(expr, j + 1, val, val);
                } else { // 枚举符号
                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val);
                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val);
                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val);
                }
            }
            expr.resize(signIndex);//注意这里，退出递归后要恢复当前表达式。撤销递归后选择。
        };
        string expr;
        backtrack(expr, 0, 0, 0);
        return ans;
    }
};

这里处理乘法很麻烦，关键在于backtrack(expr,i+1,res-mul+mul*curr,mul*curr); 这句，对于同一个式子，计算表达式的结果，和最后一个乘积的值，可以直接按从左到右的顺序求出有乘法的表达式。

注意：

1. 这里撤销选择的方式，可以理解为如下：

// 枚举符号
expr[signIndex] = '+'; 
backtrack(expr, j + 1, res + val, val);
expr[signIndex] = '-'; //更换表达式expr op val中的op字段
backtrack(expr, j + 1, res - val, -val);
expr[signIndex] = '*'; //更换表达式expr op val中的op字段，
backtrack(expr, j + 1, res - mul + mul * val, mul * val);
expr.resize(signIndex);//撤销所有选择，可以考虑连续两次递归

1. 这里j == i || num[i] != '0'的意思是如果当前位'0'，那么循环只到当前结束(j==i)，否则可以继续。

复杂度分析

时间复杂度：#card=math&code=O%284%5En%29&id=qnVFy)，其中 n 是字符串 的长度。由于在数字之间可以选择不添加符号、添加 号、 号或号，一共有 4 种选择，因此时间复杂度为 #card=math&code=O%284%5En%29&id=lWo53)。

注：考虑到将 的拷贝存入答案需要花费 #card=math&code=O%28n%29&id=vRKPV)的时间，最终的时间复杂度似乎是 #card=math&code=O%28n%20%5Ctimes%204%5En%29&id=z1FYK)。果真如此吗？考虑合法表达式最多的情况，即 全为 ，且 的情况，由于不能有前导零，我们必须在数字之间添加 三者之一，所以合法表达式有 个，因此「将 的拷贝存入答案」这一部分的时间开销至多为 #card=math&code=O%28n%20%5Ctimes%203%5En%29&id=y1YqJ)。

空间复杂度：#card=math&code=O%28n%29&id=LtUpY)。不考虑返回值的空间占用，空间复杂度取决于递归时的栈空间。