282. Expression Add Operators

这道题给出一个字符串，还有一个target，要求用这个字符串里的数字，加上+或者-或者×，使得表达式的结果是target。

这道题知道用递归来做，但是这道题很麻烦，最后还是看了别人的博客。

这道题在做之前必须意识到以下几点：

（1）参与运算的不一定是个位数，有可能是多位数，每种情况都要考虑到。

（2）多位数又带来一个问题，不能是0开头。

（3）+和-都好说，但是×的优先级大于+和-。如果前面我用了+/-，当前位置用了×，那么这个表达式的结果要恢复到没有+/-上一个数的情况，在加上当前数和上个数的乘积。

以下是参考了别人的代码，diff表示的是上一轮的操作数。如果当前这个数字前面放+，那么下一轮的diff就是cur。如果cur这个数字前面放-，那么下一轮的diff就是-cur。如果cur这个数字前面放×，那么下一轮的diff就是当前的上一轮的diff×cur，而且×cur之后，当前的结果是(curNum - diff) + diff * cur。

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        helper(num, target, 0, 0, "", res);
        return res;
    }
    void helper(string num, int target, long long diff, long long curNum, string out, vector<string>& res){
        if(num.size() == 0 && curNum == target){
            res.push_back(out);return;
        }
        for(int i = 1; i <= num.size(); ++i){
            string cur = num.substr(0, i);
            string next = num.substr(i);
            if(cur.size() > 1 && cur[0] == '0')   return;
            if(out.size() > 0){
                helper(next, target, stoll(cur), curNum + stoll(cur), out + "+" + cur, res);
                helper(next, target, -stoll(cur), curNum - stoll(cur), out + +"-"+cur, res);
                helper(next, target, diff*stoll(cur), (curNum - diff) + diff * stoll(cur), out + "*" + cur, res);
            }else{
                helper(next, target, stoll(cur), stoll(cur), cur, res);
            }
        }
    }
};