306. Additive Number

Let's observe the example first, "112358".
1st round, 1+1 = 2
2nd round, 1 + 2 = 3
3rd round, 2 + 3 = 5
4th round, 3 + 5 = 8

And let's observe the other example, "199100199"
1st round 1+ 9 = 10
2nd round 1+ 99 = 100
3rd round 99 + 100 = 199

What do you see? If there is an additive number in the substring, the additive number becomes the second number as input for next round. And we continue doing this until the following substring doesn't include the additive number or the following substring is right the additive number. Therefore, this can be done by recursion. Particularly, when calculating the sum, we should calculate by string instead of integer to avoid overflow.

1:  class Solution {  
2:  public:  
3:    bool isAdditiveNumber(string num) {  
4:      int n = num.size();  
5:      if (n < 3) return false;  
6:      for (int i = 1; i <= n/2; i++) {  
7:        for (int j = 1; j <= (n-i)/2; j++) {  
8:          if (validate(num.substr(0,i), num.substr(i,j), num.substr(i+j))) return true;  
9:        }  
10:      }  
11:      return false;  
12:    }  
13:    bool validate(string n1, string n2, string ns) {  
14:      if ((n1.size() > 1 && n1[0] == '0') || (n2.size() > 1 && n2[0] == '0')) return false;  
15:      string sum = add(n1, n2);  
16:      if (sum == ns) return true;  
17:      if (sum.size() > ns.size()) return false;  
18:      string ss = ns.substr(0, sum.size());  
19:      if (ss == sum) return validate(n2, sum, ns.substr(sum.size()));  
20:      else return false;  
21:    }  
22:    string add(string n1, string n2) {  
23:      int i = n1.size()-1, j = n2.size()-1, carry = 0;  
24:      string res;  
25:      while (i >= 0 && j >= 0) {  
26:        int sum = n1[i--]-'0' + n2[j--]-'0'+carry;  
27:        carry = sum / 10;  
28:        res.push_back(sum%10+'0');  
29:      }  
30:      while (i >= 0) {  
31:        int sum = n1[i--]-'0'+carry;  
32:        carry = sum / 10;  
33:        res.push_back(sum%10+'0');  
34:      }  
35:      while (j >= 0) {  
36:        int sum = n2[j--]-'0'+carry;  
37:        carry = sum / 10;  
38:        res.push_back(sum%10+'0');  
39:      }  
40:      if (carry) res.push_back(carry+'0');  
41:      reverse(res.begin(), res.end());  
42:      return res;  
43:    }  
44:  };