282. Expression Add Operators

Given a string that contains only digits0-9and a target value, return all possibilities to addbinaryoperators (not unary)+,-, or*between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

S: DFS

加法减法延迟一步执行，乘法立即执行。注意处理0开头的数

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        if (num.size() < 2) return result;
        for (int i = 1; i <= num.size(); ++i) {
            string s = num.substr(0, i);
            dfs(num, s , i, 0, stoll(s), '+', target);
            if (num[0] == '0') break;
        }
        return result;
    }
    void dfs(string num, string curStr, int start, long beforeSum, long beforeNum, char beforeOp, int target) {
        if(start == num.size()) {
            if (beforeOp == '+') {
                beforeSum += beforeNum;
            } else if (beforeOp == '-') {
                beforeSum -= beforeNum;
            } 
            if (beforeSum == target && curStr.size() > 0) {
                result.push_back(curStr);
            }
            return;
        }
        int n = num.size();
        int newSum = beforeSum;
        if (beforeOp == '+') {
            newSum += beforeNum;
        } else if (beforeOp == '-') {
            newSum -= beforeNum;
        }
        for (int i = 1; i <= n - start; ++i) {
            string cur = num.substr(start, i);
            int curNum = stoi(cur);
            dfs(num, curStr + '*' + cur, start + i, beforeSum, beforeNum * curNum, beforeOp, target);
            dfs(num, curStr + '+' + cur, start + i, newSum, curNum, '+', target);
            dfs(num, curStr + '-' + cur, start + i, newSum, curNum, '-', target);
            if (num[start] == '0') {
                break;
            }
        }
    }
private:
    vector<string> result;
};