306. Additive Number

https://leetcode.com/problems/additive-number/

Solution:
use DSF strategy. It is kinds of brute force implementation. As long as one is found (or reaching to the end of the string in the DSF search), return true. After all tries, return false. For the overflow, can use string instead of integer for the adding. See code below.

Code:

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int l = num.size();
        if(l<3) return false;
        for(int i=1; i<l-1; ++i){
            for(int j=i+1; j<l; ++j){
                string s1 = num.substr(0, i);
                string s2 = num.substr(i, j-i);
                if(dsf(num, j, s2, add(s1, s2))) return true;
                if(num[i] == '0') break;
            }
            if(num[0] == '0') break;
        }
        return false;
    }
private:
    bool dsf(string num, int ind, string s1, string s2){
            if(num.size()-ind < s2.size()) return false;
            if(num.substr(ind) == s2) return true;
            for(int i=0; i<s2.size(); ++i){
                if(s2[i] != num[ind+i]) return false;
            }
            ind += s2.size();
            return dsf(num, ind, s2, add(s1, s2));
        }
    string add(string s1, string s2){
        if(s1.size()>s2.size()) return add(s2, s1);
        if(s1.empty()) return s2;
        string res;
        int carrier = 0;
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        for(int i=0; i<s1.size(); ++i){
            int t = carrier + (s1[i]-'0') + (s2[i] - '0');
            carrier = t/10;
            t %= 10;
            res.push_back(t+'0');
        }
        for(int i=s1.size(); i<s2.size(); ++i){
            int t = carrier + s2[i] - '0';
            carrier = t/10;
            t %= 10;
            res.push_back(t+'0');
        }
        if(carrier) res.push_back(carrier+'0');
        reverse(res.begin(), res.end());
        return res;
    }
};