Expression Add Operators

Total Accepted: 5561 Total Submissions: 26048 Difficulty: Hard

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

 (M) Evaluate Reverse Polish Notation (M) Basic Calculator (M) Basic Calculator II (M) Different Ways to Add Parentheses

 

class Solution {
public:
    void dfs(string nums,int nums_size,int start_pos,vector<string>& res, int target,string &one_res,long long int total_res,long long int exp_res,char pre_op)
    {
        for(int i=start_pos;i<nums_size;i++){
            if(i>start_pos && nums[start_pos]=='0'){
                return;
            }
            long long  int num = 0;
            for(int j=start_pos;j<=i;j++){
                num = num*10+(nums[j]-'0');
            }
            int one_res_size = one_res.size();
            if(start_pos!=0){
                one_res.push_back(pre_op);
            }
            one_res += nums.substr(start_pos,i-start_pos+1);
            long long int tmp_exp_res = exp_res;
            switch(pre_op){
                case '*' : exp_res *= num; break;
                case '-' : exp_res = -num; break;
                case '+' : exp_res =  num; break;
            }
            if(i+1==nums_size){
                if(total_res+exp_res == target){
                    res.push_back(one_res);
                }
            }else{
                dfs(nums,nums_size,i+1,res,target,one_res,  total_res,         exp_res, '*');
                dfs(nums,nums_size,i+1,res,target,one_res,  total_res+exp_res, 0,       '+');
                dfs(nums,nums_size,i+1,res,target,one_res,  total_res+exp_res, 0,       '-');
            }
            one_res.erase(one_res.begin()+one_res_size,one_res.end());
            exp_res = tmp_exp_res;
        }
    }
    vector<string> addOperators(string nums, int target) {
        int nums_size = nums.size();
        vector<string> res;
        string one_res;
        dfs(nums,nums_size,0,res,target,one_res,0,0,'+');
        return res;
    }
};

Next challenges: (M) Evaluate Reverse Polish Notation (M) Different Ways to Add Parentheses