Elegant 0ms backtracking solution in C++ with explanation


  • 0
    G

    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 to_string(-1);
        
        return (carry) ? "1" + res : res;
    }
    
    bool isAdditive(string &num, string v1, string v2, int idx, int n){
        string sumStr = strAdd(v1, v2);
        if(num.compare(idx, sumStr.size(), sumStr) == 0)
            return (idx + sumStr.size() >= n || isAdditive(num, v2, sumStr, idx+sumStr.size(), n));
        else
            return false;
    }
    
    bool isAdditiveNumber(string num) {
        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;
    }

  • 0
    N

    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?


  • 0
    G

    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().


Log in to reply
 

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