这道题确实是困难难度。思路不难，但是细节特别多。
看完题目，首先的反应就是用回溯来解决。在用回溯的时候，要注意：
- 运算符是放在数字前还是数字后，如果放在数字前，那么第一个数字要特殊处理；如果放在数字后，那么最后一个数字要特殊处理。我这次选择的是放在数字前。
- 在回溯函数的参数设计时，要考虑好我们回溯需要哪些参数。
- 是边回溯边计算最终结果，还是将字符串组织完成再进行计算。我个人比较习惯将字符串组织完成再进行计算，但是在实际做题时发现组织完成后再计算会超时，所以这里还是边回溯边计算，可以节省时间。
- 在组织字符串时需要注意前置0是要排除的。
- 怎么记录track，根据我这次做的经验，如果是从空的字符串push back的复杂度会高一些。题解的方法很巧妙，没有办法一步想到，需要优化后去做。
- 在运算过程中可能会溢出，所以用
long来存储中间结果。
整个backtrack的框架如下：
void backtrack(string num, int target,string track,int idx, char op){
if(idx==num.length()){
if(compute(track,0,0,0)==target){
res.push_back(track);
}
return;
}
if(idx==0){
track.push_back(num[idx]);
for(int i=0;i<4;++i){
// 排除前置0
if(num[idx]=='0'&&i==0){
continue;
}
backtrack(num,target,track,idx+1,ops[i]);
}
}
else{
if(op!=' '){
track.push_back(op);
}
track.push_back(num[idx]);
// 当idx为最后一位数的时候，不需要再遍历ops
if(idx==num.length()-1){
backtrack(num,target,track,idx+1,ops[0]);
}
else{
for(int i=0;i<4;++i){
// 排除前置0
if(op!=' '&&num[idx]=='0'&&i==0){
continue;
}
backtrack(num,target,track,idx+1,ops[i]);
}
}
}
}
vector<string> addOperators(string num, int target) {
string track;
ops=" +-*";
// 因为第一个数字不会加上op，所以这里放哪个op都可以
backtrack(num,target,track,0,ops[0]);
return res;
}
在拿到字符串表达式后，我们需要计算表达式的结果与target进行比较，那么如何计算就成为了一个问题。有两个思路，一个是用栈来计算表达式的值，另一个就是直接从左往右顺序计算表达式。用栈来计算应该都比较熟悉，但是根据我自己做题的结果来看，复杂度会更高。下面主要写从左到右运算的方法。
从左到右顺序算表达式
如果想从左到右顺序计算，我们需要明白我们在计算过程中至少需要几个参数：
| 表达式 | cur | prev |
|---|---|---|
| 2 | 2 | 2 |
| 2+51 | 2+51=53 | 51 |
| 2+51*3 | 53-51+51*3=155 | 51*3=153 |
| 2+51*3*2 | 155-153+153*2=308 | 153*2=306 |
由此我们可以知道，上述我们的做法是不行的，因为一旦不能确定数的位数，两个参数都不够，因此我们回溯时的选择不是四个，而是只有三个运算符。
用push back记录track来实现
class Solution {
private:
vector<string> ans;
string ops;
public:
void backtrack(string num,int target,string track,int idx,long cur,long prev){
if(idx==num.length()){
if(target==cur){
ans.push_back(track);
}
return;
}
// 第一位不能添加符号
if(idx==0){
long val=0;
for(int i=idx;i<num.length();++i){
if(num[idx]=='0'&&i>idx){
break;
}
val=val*10+num[i]-'0';
track.push_back(num[i]);
backtrack(num,target,track,i+1,val,val);
}
}
else{
for(int i=0;i<3;++i){
// 用tmp存储回溯之前的track状态
string tmp=track;
track.push_back(ops[i]);
long val=0;
int j=idx;
for(;j<num.length();++j){
// 排除前置0
if(num[idx]=='0'&&j>idx){
break;
}
val=val*10+num[j]-'0';
track.push_back(num[j]);
if(ops[i]=='+'){
backtrack(num,target,track,j+1,cur+val,val);
}
else if(ops[i]=='-'){
backtrack(num,target, track,j+1,cur-val,-val);
}
else{
backtrack(num,target,track,j+1,cur-prev+prev*val,prev*val);
}
}
// 做完选择，需要还原track
track=tmp;
}
}
}
vector<string> addOperators(string num, int target) {
string track;
ops="+-*";
backtrack(num,target,track,0,0,0);
return ans;
}
};