1、描述

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

示例 1:

输入: num = “123”, target = 6
输出: [“1+2+3”, “123”]
示例 2:

输入: num = “232”, target = 8
输出: [“23+2", "2+32”]
示例 3:

输入: num = “105”, target = 5
输出: [“1*0+5”,“10-5”]
示例 4:

输入: num = “00”, target = 0
输出: [“0+0”, “0-0”, “0*0”]

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、关键字

添加运算符，表达式，

3、思路

一眼就是回溯

4、notes

不太会写

6、code

class Solution {
    using ll = long long;
public:
    string num;
    vector<string> ret;
    int n, target;

    void backtrack(string &s, int index, ll res, ll mul) {
        // 当前已达到字符串末尾，若结果正确，则加入结果数组
        // 不论正确与否，都应返回
        if (index == n) {
            if (res == target) {
                ret.emplace_back(s);
            }
            return;
        }

        // 当前表达式长度
        int m = s.size();
        if (index > 0) {
            s.push_back(0); // 占位，下面填充符号
        }
        ll val = 0;
        // 枚举截取的数字长度（取多少位），注意数字可以是单个 0 但不能有前导零
        for (int j = index; j < n && (j == index || num[index] != '0'); ++j) {
            val = val * 10 + num[j] - '0';
            s.push_back(num[j]);
            if (index == 0) { // 表达式开头不能添加符号
                backtrack(s, j + 1, val, val);
            } else { // 枚举符号
                // 加法
                s[m] = '+'; backtrack(s, j + 1, res + val, val);
                // 减法
                s[m] = '-'; backtrack(s, j + 1, res - val, -val);
                // 乘法
                s[m] = '*'; backtrack(s, j + 1, res - mul + mul * val, mul * val);
            }
        }
        s.resize(m);
    };

    vector<string> addOperators(string _num, int _target) {
        num = _num;
        n = _num.length();
        target = _target;
        string s;
        backtrack(s, 0, 0, 0);
        return ret;
    }
};