text: /*
   * @lc app=leetcode id=306 lang=cpp
   *
   * [306] Additive Number
   */
  
  // @lc code=start
  class Solution {
  public:
      bool isAdditiveNumber(string num) {
          if (num.size() < 3) return false; 
          for (int i = 1; i <= num.size()/2; i++) {
              for (int j = 1; j <= (num.size()-i)/2; j++){
                  if(check(num, i, j)) return true;
              }
          }
          return false;
      }
  
      string add(string a, string b) {
          string res;
          int i = a.size()-1, j = b.size()-1, carry = 0;
          while (i >= 0 || j >= 0 || carry > 0){
              int sum = carry + (i>=0 ? (a[i--]-'0') : 0) + (j>=0?  (b[j--]-'0') : 0);
              res.push_back(sum%10+'0');
              carry=sum/10;
          }
          reverse(res.begin(), res.end());
          return res;
      }
  
      bool check(string num, int i, int j) {
          if (num[0] == '0' && i > 1) return false;
          if (num[i] == '0' && j > 1) return false;
          string x1 = num.substr(0, i);
          string x2 = num.substr(i, j);
          string sum;
          for (int start = i + j; start != num.size(); start += sum.size()) {
              sum = add(x1, x2);
              x1 = x2;
              x2 = sum;
              if (i+j+sum.size() > num.size()) return false;
              if (i+j+sum.size() <= num.size() && sum.compare(num.substr(start, sum.size())) != 0) return false;
          }
          return true;
      }
  };
  // @lc code=end
  
  