class Solution {
public:
    bool isValid(string num)
    {
        if (num.size() > 1 && num[0] == '0')
            return false;
        return true;
    }
    
    int val(string a, int pos)
    {
        if (pos >= a.length())
            return 0;
  
        //  converting character to integer
        return (a[pos] - '0');
    }
    
    string addString(string a, string b)
    {
        string sum = "";
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
  
        //  loop untill both string get processed
        while (i >= 0 || j >= 0)
        {
            int t = val(a, i) + val(b, j) + carry;
            sum += (t % 10 + '0');
            carry = t / 10;
            i--;    j--;
        }
        if (carry)
            sum += (carry + '0');
        reverse(sum.begin(), sum.end());
        return sum;
    }
    
    bool checkAddition(list<string>& res, string a,
                             string b, string c)
    {
        //  both first and second number should be valid
        if (!isValid(a) || !isValid(b))
            return false;
        string sum = addString(a, b);
  
        //  if sum is same as c then direct return
        if (sum == c)
        {
            res.push_back(sum);
            return true;
        }
  
        /*  if sum size is greater than c, then no
        possible sequence further OR if c is not
        prefix of sum string, then no possible
        sequence further  */
        if (c.size() <= sum.size() ||
            sum != c.substr(0, sum.size()))
            return false;
        else
        {
            res.push_back(sum);
          
            //  next recursive call will have b as first
            //  number, sum as second number and string
            //  c as third number after removing prefix
            //  sum string from c
            return checkAddition(res, b, sum,
                             c.substr(sum.size()));
        }
    }
    
    bool isAdditiveNumber(string num) {
        list<string> res;
        int l = num.length();
  
        // loop untill l/2 only, because if first
        // number is larger,then no possible sequence
        // later
        for (int i = 1; i <= l/2; i++)
        {
            for (int j = 1; j <= (l - i)/2; j++)
            {   
                if (checkAddition(res, num.substr(0, i),
                              num.substr(i, j),
                              num.substr(i + j))) {
                    return true;
                }
            }
        }
        return false;
    }
};