LeetCode 282. 给表达式添加运算符

LeetCode 282. 给表达式添加运算符
思路：

参考

• 下一个运算符是+, 那么a+b×( c )+()=(a+b×c)+1×();
• 下一个运算符是-, 那么a+b×( c )−()=(a+b×c)+(−1)×();
• 下一个运算符是*, 那么a+b×( c )×()=a+(b×c)×();

代码：

class Solution {
public:
    vector<string> ans;
    string path;
    vector<string> addOperators(string num, int target) {
        path.resize(100);
        dfs(num, 0, 0, 0, 1, target);
        return ans;
    }

    void dfs(string& num, int u, int len, long long a, long long b, int target) {
        if (u == num.size()) {
            if (a == target) {
                ans.push_back(path.substr(0, len - 1));
            }
            return;
        } 

        long long c = 0;
        for (int i = u; i < num.size(); i ++ ) {
            //前导0
            if (i != u && num[u] == '0') break;
            c = c * 10 + num[i] - '0';
            path[len ++ ] = num[i];
            path[len] = '+';
            dfs(num, i + 1, len + 1, a + b * c, 1, target);
            if (i + 1 < num.size()) {
                path[len] = '-';
                dfs(num, i + 1, len + 1, a + b * c, -1, target);
            }
            if (i + 1 < num.size()) {
                path[len] = '*';
                dfs(num, i + 1, len + 1, a, b * c, target);
            }
        }
    }
};