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

Credits:
Special thanks to @davidtan1890 for adding this problem and creating all test cases.

backtracking, DFS.

Use a tree to evaluate current expression. If we meet a * or concatenate operation, use the parameters curNum and curMulRe(current multiple result) to retrieve previous result and evaluate current result.

There are many many tricky corners we should handle here.

```class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string> ans;
if(num.size() == 0) return ans;
DFS(num, 1, num[0] - '0', num[0] - '0', num[0] - '0', '+', target, to_string(num[0] - '0'), ans);
return ans;
}
void DFS(string num, int pos, long eval, long curNum, long curMulRe, char prevOperator, int target, string path, vector<string>& ans){
//leaf node
if(pos == num.size()){
if(eval == target){
ans.push_back(path);
}
return ;
}

int digit = num[pos] - '0';
//concatenate
path.push_back(num[pos]);
if(curNum != 0){
switch(prevOperator){
case '+':
DFS(num, pos + 1, eval - curNum + (curNum * 10 + digit), curNum * 10 + digit, curNum * 10 + digit, prevOperator, target, path, ans);
break;
case '-':
DFS(num, pos + 1, eval + curNum - (curNum * 10 + digit), curNum * 10 + digit, curNum * 10 + digit, prevOperator, target, path, ans);
break;
case '*':
DFS(num, pos + 1, eval - curMulRe + curMulRe / curNum * (curNum * 10 + digit), curNum * 10 + digit, curMulRe / curNum * (curNum * 10 + digit),prevOperator, target, path, ans);
break;
}

}
path.pop_back();

//+ operator
path.push_back('+');
path.push_back(num[pos]);

DFS(num, pos + 1, eval + digit, digit, digit, '+', target, path, ans);

path.pop_back();
path.pop_back();
//- operator
path.push_back('-');
path.push_back(num[pos]);

DFS(num, pos + 1, eval - digit, digit, digit, '-', target, path, ans);

path.pop_back();
path.pop_back();

//*operator
path.push_back('*');
path.push_back(num[pos]);

switch(prevOperator){
case '+':
DFS(num, pos + 1, eval - curNum + curNum * digit, digit, curNum * digit, '*', target, path, ans);
break;
case '-':
DFS(num, pos + 1, eval + curNum - curNum * digit, digit, -curNum * digit, '*', target, path, ans);//Be careful!!!! curMulRe should be "-curNum * digit"
break;
case '*':
DFS(num, pos + 1, eval - curMulRe + curMulRe * digit, digit, curMulRe * digit, '*', target, path, ans);
break;
}

path.pop_back();
path.pop_back();
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.