# Elegant 0ms backtracking solution in C++ with explanation

• Straightforward backtracking solution,

• Backtracking function takes two numbers v1, v2 in string and idx of next start position.
• Recurse further only when subsequent substring equals to expected sum of v1, v2.
• Helper function to add two strings to avoid possible overflow.
• One side note, usually the base case handling should be the first thing in recursion function, which is
`idx >= num.length()`. However, that will cause a small problem for test case like `"10"`. The small trick to handle it is by moving base case after we found expecting substring of (v1+v2) in num.

Here is my resolution,

``````string strAdd(string &v1, string &v2){
string res = "";
int carry = 0;
int len1 = v1.size(), len2 = v2.size();

for(int i = len1-1, j = len2-1; i >= 0 || j >= 0; i--, j--){
int n1 = (i >= 0) ? v1[i]-'0' : 0;
int n2 = (j >= 0) ? v2[j]-'0' : 0;
res = to_string((n1 + n2 + carry) % 10) + res;
carry = (n1 + n2 + carry) > 9;
}
if((v1[0] == '0' && len1 > 1) ||(v2[0] == '0' && len2 > 1))

return (carry) ? "1" + res : res;
}

bool isAdditive(string &num, string v1, string v2, int idx, int n){
if(num.compare(idx, sumStr.size(), sumStr) == 0)
return (idx + sumStr.size() >= n || isAdditive(num, v2, sumStr, idx+sumStr.size(), n));
else
return false;
}

int n = num.size();
bool found = 0;

for(int len1 = 1; len1 <= (n/2); len1++){
for(int len2 = 1; len2 <= (n/2); len2++){
found = isAdditive(num, num.substr(0, len1), num.substr(len1, len2), len1+len2, n);
if(found)
return true;
}
}
return false;
}``````

• Nice solution but feels like there is a bug in the code. I tried case "10910", your code returned true, but it should be false since "09" is considered invalid so that 1+09=10 is not a valid combination. Your solution is accepted though, maybe Leetcode doesn't have enough test cases?

• Thanks for pointing it out! Yes my code didn't handle the case when invalid leading "0" is in the first two candidate strings. So I added the check of (v1[0] == '0' && len1 > 1) ||(v2[0] == '0' && len2 > 1) explicitly in strAdd().

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