### Solution

#### Analysis

Typical backtracking problem as it is. Try to split the string into small blocks and then meantime try different operators among them.

- from a starting position, we can try different valid length for the current number but if the length is bigger than 1 and the first digit is zero then just stop;
- using different operators to connect the current number, calculate and then store them in a temporary string for the next number till the end;
- but when we try
`*`

, we have to be more careful since multiplier will associate its previous number and has higher precedence, so we as a result have to record its previous number; but this will require us to handle it delicately when we are inserting`+ or -`

, as for`+`

we can just put the number as previous but as to`-`

, we will need to set`-number`

as previous; because we have to subtract the previous number first when inserting`*`

- inserting means we are do the calculation with the current number here; - since the target is an
`int`

, so when the number is larger than INT_MAX, we should just stop there.

#### Improvements

- there will be numbers collected larger than INT_MAX, so we have to adopt
`long`

- long long here is unnecessary; - collecting the number one character at a time is more efficient to convert the substring directly to integer using
`stol`

; - using temporary substring to replace
`to_string(number)`

will save lots of converting time; - actually we can just use one temporary string and append the digit instead of retrieving the substring each time.

The whole solution in C++ is as follows.

```
class Solution {
private:
int sLen;
void traverse(const string s, int pos, long current, long pre, int sum, string path, vector<string>& v)
{
if(sLen == pos) { if(current == sum) v.push_back(path); return ; }
long num = 0;
string t;
for(int i = pos; i < sLen; ++i)
{
if(i-pos>0 && s[pos]=='0') return ;
t += s[i];
num = 10*num + s[i]-'0';
if(num > INT_MAX) return ;
if(pos == 0) traverse(s, i+1, num, num, sum, t, v);
else
{
traverse(s, i+1, current+num, num, sum, path+"+"+t, v);
traverse(s, i+1, current-num, -num, sum, path+"-"+t, v);
traverse(s, i+1, current-pre+pre*num, pre*num, sum, path+"*"+t, v);
}
}
}
public:
vector<string> addOperators(string s, int target) {
sLen = s.length();
vector<string> v;
traverse(s, 0, 0, 0, target, "", v);
return v;
}
};
```

Always welcome new ideas and `practical`

tricks, just leave them in the comments!