题目：
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (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 -> []

题目看上去有点像dp，但又无法表示状态。
又发现要求输出所有结果，果断爆搜了。
思想就是每次在当前串后面添加一个运算符，显然加减号可以直接添加，然后可以很方便更新当前计算结果。
但乘法则需要考虑前面的数字是什么，所以需要在搜索过程中添加一个新的域：last_val。
设当前运串后添加了“x”，则计算结果增量为last_val(x-1)。
其中x之所以减1是因为last_val在当前计算结果中已经包含一份了，所以增量就是x-1份last_val。

class Solution {
public:
    vector<string> ans;
    vector<string> addOperators(string num, int target) {
        ans.clear();
        for (int i = 0; i < num.length(); i++) {
            string sub_str = num.substr(0, i + 1);
            long long x = toNumber(sub_str);
            calc(num, i + 1, sub_str, x, x, target);
            if (i == 0 && num[i] == '0') break;
        }
        return ans;
    }

    void calc(string num, int start, string cur_str, long long cur_val, long long last_val, long long target) {
        if (start >= num.length()) {
            if (cur_val == target) ans.push_back(cur_str);
            return;
        }
        for (int i = start; i < num.length(); i++) {
            string sub_str = num.substr(start, i - start + 1);
            long long x = toNumber(sub_str);
            calc(num, i + 1, cur_str + "+" + sub_str, cur_val + x, x, target);
            calc(num, i + 1, cur_str + "-" + sub_str, cur_val - x, -x, target);
            calc(num, i + 1, cur_str + "*" + sub_str, cur_val + last_val * (x - 1), last_val * x, target);
            if (i == start && num[i] == '0') break;
        }
    }

    long long toNumber(string s) {
        long long rt = 0;
        for (int i = 0; i < s.length(); i++)
            rt = rt * 10 + s[i] - '0';
        return rt;
    }
};