An additive number is a string whose digits can form an additive sequence.

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

Given a string containing only digits, return true if it is an additive number or false otherwise.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

&nbsp;
Example 1:

Input: "112358"
Output: true
Explanation: 
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


Example 2:

Input: "199100199"
Output: true
Explanation: 
The additive sequence is: 1, 99, 100, 199.&nbsp;
1 + 99 = 100, 99 + 100 = 199


&nbsp;
Constraints:


	1 &lt;= num.length &lt;= 35
	num consists only of digits.


&nbsp;
Follow up: How would you handle overflow for very large input integers?

class Solution:
def isAdditiveNumber(self, num: str) -> bool:
    
    def isadditive(num1,num2,st):
        if len(st) == 0:
            return True
        num3 = str(num1+num2)
        l = len(num3)
        return num3 == st[:l] and isadditive(num2,int(num3),st[l:])
    
    for i in range(1,len(num)-1):
        for j in range(i+1,len(num)):
            if num [0] == "0" and i != 1:
                break
            if num[i] == "0" and i+1 != j:
                break
           
            if isadditive(int(num[:i]),int(num[i:j]),num[j:]):
                
                return True
    return False
class Solution {

    public boolean isAdditiveNumber(String num) {
        return backtrack(num, 0, 0, 0, 0);
    }
    
    public boolean backtrack(String num, int idx, long sum, long prev, int length){
        if(idx == num.length()){
            return length >= 3;
        }
        
        long currLong = 0;
        
        for(int i = idx; i < num.length(); i++){
            //make sure it won't start with 0
            if(i > idx && num.charAt(idx) == '0') break;
            currLong = currLong * 10 + num.charAt(i) - '0';
            
            if(length >= 2){
                if(sum < currLong){
                    //currLong is greater than sum of previous 2 numbers
                    break;
                }else if(sum > currLong){
                    //currLong is smaller than sum of previous 2 numbers
                    continue;
                }
            }
            //currLong == sum of previous 2 numbers
            if(backtrack(num, i + 1, currLong + prev, currLong, length + 1) == true){
                return true;
            }
        }
        return false;
    }
}
class Solution
{
public:
    bool isAdditiveNumber(string num)
    {
        vector<string> adds;
        return backtrack(num, 0, adds);
    }

private:
    bool backtrack(string num, int start, vector<string> &adds)
    {
        if (start >= num.size() && adds.size() >= 3)
            return true;

        int maxSize = num[start] == '0' ? 1 : num.size() - start;
        for (int i = 1; i <= maxSize; i++)
        {
            string current = num.substr(start, i);

            if (adds.size() >= 2)
            {
                string num1 = adds[adds.size() - 1], num2 = adds[adds.size() - 2];
                string sum = add(num1, num2);
                if (sum != current)
                    continue;
            }

            adds.push_back(current);
            if (backtrack(num, start + i, adds))
                return true;
            adds.pop_back();
        }
        return false;
    }

    string add(string num1, string num2)
    {
        string sum;
        int i1 = num1.size() - 1, i2 = num2.size() - 1, carry = 0;
        while (i1 >= 0 || i2 >= 0)
        {
            int current = carry + (i1 >= 0 ? (num1[i1--] - '0') : 0) + (i2 >= 0 ? (num2[i2--] - '0') : 0);
            carry = current / 10;
            sum.push_back(current % 10 + '0');
        }
        if (carry)
            sum.push_back(carry + '0');
        reverse(begin(sum), end(sum));
        return sum;
    }
};
const getNum = (str, i, j) => {
    str = str.slice(i, j);
    if(str[0] == '0' && str.length > 1) return -1000
    return Number(str);
}

var isAdditiveNumber = function(num) {
    // i = 3 say and make theory and proof that
    const len = num.length;
    for(let b = 2; b < len; b++) {
        for(let i = 0; i < b - 1; i++) {
            for(let j = i + 1; j < b; j++) {
                let v1 = getNum(num,0, i + 1);
                let v2 = getNum(num,i + 1, j + 1);
                let v3 = getNum(num,j + 1, b + 1);
                if(v1 + v2 == v3) {
                    // test hypothesis;
                    // from b start checking if string persist behaviour
                    let p = num.slice(0, b + 1);
                    while(p.length <= len) {
                        let sum = v2 + v3;
                        p += sum;
                        v2 = v3;
                        v3 = sum;
                    }
                    if(p.slice(0, len) == num) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
};
Additive Number