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();
    }
};