## Thursday, July 20, 2017

### [Leetcode] Expression Add Operators, Solution

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 -> []```

[Thoughts]

[Code]

``````1:    vector<string> addOperators(string num, int target) {
2:      vector<string> result;
3:      if(num.size() == 0) return result;
4:
5:      nextStep(num, 0, target, 0, "", 0, result);
6:      return result;
7:    }
8:
9:    void nextStep(string& numStr, int cur_index, int& target, long value, string equation, long pre_num, vector<string>& result) {
10:      if(value == target && cur_index == numStr.size()) {
11:        result.push_back(equation);
12:        return;
13:      }
14:
15:      for(int i = 1; i< numStr.size() - cur_index +1; i++) {
16:        if(i >1 && numStr[cur_index] == '0') break;
17:        string temp = numStr.substr(cur_index, i);
18:        long num = stol(temp);
19:
20:        if(cur_index == 0){
21:          nextStep(numStr, cur_index +i, target, num, temp, num, result);
22:          continue;
23:        }
24:
25:        nextStep(numStr, cur_index +i, target, value + num, equation + '+' + temp, num, result);
26:        nextStep(numStr, cur_index +i, target, value - num, equation + '-' + temp, -num, result);
27:        nextStep(numStr, cur_index +i, target, value - pre_num + pre_num * num, equation + '*' + temp, pre_num * num, result);
28:      }
29:    }
``````