题解 | #给表达式添加运算符#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @param target int整型 
     * @return string字符串vector
     */
     //+ - *
   //cur 记录当前值，
    vector<string> addOpt(string num, int target) {
        // write code here
        int n=num.size();
        vector<string> res;
        string s;//初始化第一个位置的值
        s+=num[0];
        int cur=num[0]-'0';
        dfs(1,cur,target,num,s,res);
        return res;
    }
    void dfs(int j,int cur,int target,string num,string s,vector<string> &res){//注意res需要取地址
        string temp=s;
        int temp2=cur;
        if(cur==target&&j==num.size()){
            res.push_back(s);
            return;
        }
        if(j>num.size()){
            return;
        }
        //每层递归循环测试+ - *三种可能性
        for(int i=0;i<3;i++){
            if(i==0){
                s+='+';
                cur=cur+int(num[j]-'0');                
                s+=num[j];
                dfs(j+1,cur,target,num,s,res);
                //递归运行完后需要将参数调回来
                s=temp;
                cur=temp2;
            }
            if(i==2){
                s+='-';
                cur=cur-int(num[j]-'0');
                s+=num[j];
                dfs(j+1,cur,target,num,s,res);
                s=temp;
                cur=temp2;
            }
            if(i==1){
                s=s+'*';
                cur=cur*int(num[j]-'0'); 
                s+=num[j];
                dfs(j+1,cur,target,num,s,res);
                s=temp;
                cur=temp2;
            }
            }
    

    }
};