# Typical backtracking solution with detailed explanation in C++

• ### 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!

• @LHearen
I have a question regarding to this statement:
"since the target is an int, so when the number is larger than INT_MAX, we should just top there."
I think we cannot give up here, because if we choose '-' as the next symbol, we still have change to come back from "long domain" to "int domain". Isn't this true?

• @quesder Sorry about the wrong typing `stop there`, though I didn't quite get your point, but we have to stop there since the target is an int which implies that the numbers in the calculation process should also follow the rule `int type`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.