题目：
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 -> []思路：
本题算是一道比较难的回溯题目了。在进行搜索的时候当前一位可以和后面的数字组成一个数，也可以直接从这里分割和后面的数字进行运算．在进行运算的时候需要二个数字，我们可以先保存路径，将当前运算符记录下来，等待下一个数字的时候的把运算符和下一个数字进行运算．即如果运算符为加号，我们只需要保存一个1，在和下一个数字运算只要乘１就行，然后将其值保存在结果中．同理对于减只要和下一个数字乘以-1．对于乘号我们需要保存一个用于乘的当前数字（一旦决定要乘，还需要对sum恢复原貌）。这里的代码有点费解，需要好好理解。
代码：
class Solution { public: vector<string> addOperators(string num, int target) { if(num.size() == 0) { return {}; } vector<string> ret; DFS(ret, num, -target, "", 0, 0); return ret; } private: void DFS(vector<string> &ret, string &num, long sum, string path, int k, int pre) { if(k == num.size() && sum == 0) { return ret.push_back(path); } int val = 0; for(int i = k; i < num.size(); i++) { val = val * 10 + (num[i] - '0'); if(val > INT_MAX) { break; } if(k == 0) { // the operator before the string can only be treated as '+' DFS(ret, num, sum + val, path + to_string(val), i+1, val); } else { DFS(ret, num, sum + val, path + "+" + to_string(val), i+1, val); DFS(ret, num, sum - val, path + "-" + to_string(val), i+1, -val); DFS(ret, num, sum - pre + pre * val, path + '*' + to_string(val), i+1, pre * val); } if(num[k] == '0') { // if num[k] == '0', then val can only be 0, not 0xxx break; } } } };