<p>An <strong>additive number</strong> is a string whose digits can form an <strong>additive sequence</strong>.</p>

<p>A valid <strong>additive sequence</strong> should contain <strong>at least</strong> three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.</p>

<p>Given a string containing only digits, return <code>true</code> if it is an <strong>additive number</strong> or <code>false</code> otherwise.</p>

<p><strong>Note:</strong> Numbers in the additive sequence <strong>cannot</strong> have leading zeros, so sequence <code>1, 2, 03</code> or <code>1, 02, 3</code> is invalid.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> &quot;112358&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> 
The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> &quot;199100199&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> 
The additive sequence is: 1, 99, 100, 199.&nbsp;
1 + 99 = 100, 99 + 100 = 199
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 35</code></li>
	<li><code>num</code> consists only of digits.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> How would you handle overflow for very large input integers?</p>

class Solution {
public:
    long long tranS(string x) {
        if (x.length() >= 19)
            return -1;
        long long res = 0;
        if (x[0] == '0' && x.length() == 1)
            return 0;
        if (x[0] == '0')
            return -1;
        for (int i = 0; i < x.length(); i++)
            res = res * 10 + (int)(x[i] - '0');
        return res;
    }
    bool solve(string last, string curr, string num) {
        // cout << last << " " << curr << " " << num << endl;
        if (num == "")
            return 1;
        if (tranS(last) < 0 || tranS(curr) < 0)
            return 0;
        string next = "";
        for (int i = 0; i < num.length(); i++) {
            next += num[i];
            cout << "|| next:" << next << endl;
            num.erase(0, 1);
            if (tranS(next) == tranS(last) + tranS(curr) &&
                solve(curr, next, num))
                return 1;
            i--;
        }
        return 0;
    }
    bool isAdditiveNumber(string num) {
        for (int i = 1; i < num.length() - 1; i++) {
            for (int j = i + 1; j < num.length(); j++) {
                string sub1 = num.substr(0, i);
                string sub2 = num.substr(i, j - i);
                string sub3 = num.substr(j);
                if (solve(sub1, sub2, sub3)) {
                    return 1;
                }
            }
        }
        return 0;
    }
};
10000