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

这道题除了DFS，我还没想出更好的办法。需要注意的是如何处理*号。每当尝试用*号的时候，要注意处理上一次计算。比如第二个例子 “232”，当处理到2+3的时候，值是5，这时候对于下一个数字2，如果用*号，就得把上一次计算回滚，(5 - 3) + 3*2。

除此之外，没有难点。


[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:    }