+，-，*有一种特别直接的处理方法是直接算，保存一个答案ans，pre，遇到运算符就算，遇到乘法的时候就先把之前算的减掉ans-pre+pre*cur，就这样处理即可。
typedef long long LL; class Solution { public: vector<string> addOperators(string num, int target) { string expression; helper(num,target,0,0,0,expression); return res; } vector<string> res; void helper(string num, int target, int index, LL ans, LL pre, string expression){ if(index==num.size()){ if(target==(int)ans) res.push_back(expression); return; } for(int i=index;i<num.size();i++){ string s = num.substr(index, i - index + 1); // 从index向后取出对应长度的新字符串 if(s.size() > 1 && s[0] == '0') return; // 如果第一位是0的两位数，那么跳过 long cur = stol(s); if(index==0) helper(num,target,i+1,ans+cur,cur,expression+s); else{ helper(num,target,i+1,ans+cur,cur,expression+"+"+s); helper(num,target,i+1,ans-cur,-cur,expression+"-"+s); helper(num,target,i+1,ans- pre + pre * cur, pre*cur,expression+"*"+s); } } } };将传值改成传引用，并加入回溯处理
typedef long long LL; class Solution { public: vector<string> addOperators(string num, int target) { string expression; helper(num,target,0,0,0,expression); return res; } vector<string> res; void helper(string num, int target, int index, LL ans, LL pre, string expression){ if(index==num.size()){ if(target==(int)ans) res.push_back(expression); return; } for(int i=index;i<num.size();i++){ string s = num.substr(index, i - index + 1); // 从index向后取出对应长度的新字符串 if(s.size() > 1 && s[0] == '0') return; // 如果第一位是0的两位数，那么跳过 long cur = stol(s); if(index==0) helper(num,target,i+1,ans+cur,cur,expression+s); else{ helper(num,target,i+1,ans+cur,cur,expression+"+"+s); helper(num,target,i+1,ans-cur,-cur,expression+"-"+s); helper(num,target,i+1,ans- pre + pre * cur, pre*cur,expression+"*"+s); } } } };
