<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:
    bool dfs(vector<long long> &v, const string &s, int start) {
        // for (auto elem : v) {
        //     cout << elem << " ";
        // }
        cout << endl;
        int n = s.length();
        if (start == n && v.size() > 2) {
            return true;
        }
        if (v.size() < 2) {
            for (int i = start; i < min(n, (n + 1 + start) / 2); i++) {
                if (s[start] == '0' && i > start) {
                    continue;
                }
                v.push_back(stoll(s.substr(start, i + 1 - start)));
                if (dfs(v, s, i + 1)) {
                    return true;
                }
                v.pop_back();
            }
        }
        else {
            long long sum = v[v.size() - 1] + v[v.size() - 2];
            for (int i = start; i < n; i++) {
                if (s[start] == '0' && i > start) {
                    continue;
                }
                long long tmp = stoll(s.substr(start, i - start + 1));
                if (tmp > sum) {
                    break;
                }
                // cout << "tmp: " << tmp << " " << sum << endl;
                if (tmp == sum) {
                    v.push_back(tmp);
                    if (dfs(v, s, i + 1)) {
                        return true;
                    }
                    v.pop_back();
                }
            }
        }
        return false;
    }

    bool isAdditiveNumber(string num) {
        vector<long long> v;
        return dfs(v, num, 0);
    }
};
8300