282. Expression Add Operators

My intuition is dfs. For each dfs, try one digit, two digits until the whole number. For each number, we compute the value. We take the computational value so far, do the addition, subtraction and production respectively. Addition and subtraction are straightforward, but production requires a little trick. Take "a+b*c" as example,  at position 'c',  the computational value so far is "a+b", so we need subtract b and add product of b and c. Therefore, we need to track the value for previous operation. So far, the api requires two more additional arguments: computational value so far and value for previous operation. Note, we don't have to do any operation for first number so we need to take it as special case. Also, since the number is converted from string, it's very easy to get overflow. So we must use long integer. Finally, "08" is not a valid number and we need to take care of this case. As a result, the code is as following.

1:  class Solution {  
2:  public:  
3:    vector<string> addOperators(string num, int target) {  
4:      vector<string> res;  
5:      if (num.empty()) return res;  
6:      dfs(num, target, "", res, 0, 0, 0);  
7:      return res;  
8:    }  
9:    void dfs(string &num, int target, string sol, vector<string> &res, int start, long long cur, long long prev) {  
10:      if (start == num.size()) {  
11:        if (target == cur) res.push_back(sol);  
12:        return;  
13:      }  
14:      for (int i = start; i < num.size(); i++) {  
15:        if (num[start] == '0' && i > start) break;  
16:        string s = num.substr(start, i-start+1);  
17:        // when dealing with string, be sure to use long long.  
18:        long long val = stol(s);  
19:        if (start == 0) {  
20:          // special case for first digit.  
21:          dfs(num, target, s, res, i+1, val, val);  
22:        } else {  
23:          dfs(num, target, sol+"+"+s, res, i+1, cur+val, val);  
24:          dfs(num, target, sol+"-"+s, res, i+1, cur-val, -val);  
25:          dfs(num, target, sol+"*"+s, res, i+1, cur-prev+prev*val, prev*val);  
26:        }  
27:      }  
28:    }  
29:  };