<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:
    string addStrings(string &num1,string &num2) {
    int i = num1.size() - 1;
    int j = num2.size() - 1;
    int carry = 0;
    string result ="";
    while (i >= 0 || j >= 0 || carry){
        int sum = carry;
        if (i >= 0) {
            sum += num1[i] - '0';
            i--;
        }
        if (j >= 0) {
            sum += num2[j] - '0';
            j--;
        }
        carry = sum / 10;
        result += (sum % 10) + '0';
    }
    reverse(result.begin(), result.end());
    return result;
}
bool possible(string fir,string sec,string thir,bool &flag){
    // int n=v.size();
    if(fir=="*" || sec=="*")return true;
    if(addStrings(fir,sec)==thir){
        flag=true;
        return true;
    }    
    return false;
}
bool find(int i,int &n,bool &flag,string &num,string &fir,string &sec,string &thir){
    if(i==n){
        return (fir!="*" && sec!="*" && thir!="*");
    }
    string str="";
    int end;
    end=(num[i]=='0')?1:n-i;
    for(int k=i;k<end+i;k++){
        str+=num[k];
        if(possible(fir,sec,str,flag)){
            string temp=thir;
            thir=sec;
            sec=fir;
            fir=str;
            if(find(k+1,n,flag,num,fir,sec,thir)){
                return true;
            }
            else{
                fir=sec;
                sec=thir;
                thir=temp;
            }
        }
    }
    return false;
}
bool isAdditiveNumber(string num) {
    int n=num.size();
    bool flag=false;
    string fir="*",sec="*",thir="*";
    return find(0,n,flag,num,fir,sec,thir);
}
};
10300