Additive number is a string whose digits can form additive sequence.

A valid additive sequence should containat leastthree 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'0'-'9', write a function to determine if it's an additive number.

Note:Numbers in the additive sequencecannothave leading zeros, so sequence1, 2, 03or1, 02, 3is invalid.

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
.

             1 + 99 = 100, 99 + 100 = 199

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

class Solution {
    public boolean isAdditiveNumber(String num) {
        if (num == null || num.length() < 3) return false;

        int n = num.length();
        for (int i = 1; i <= (n - 1) / 2; i++){
            if (num.charAt(0) == '0' && i >= 2) break;

            for (int j = i + 1; n - j >= i && n - j >= j - i; j++){
                if (num.charAt(i) == '0' && j >= i + 2) break;
                long num1 = Long.parseLong(num.substring(0, i));
                long num2 = Long.parseLong(num.substring(i, j));
                String rest = num.substring(j);

                if (valid(rest, num1, num2)) return true;
            }
        }

        return false;
    }

    private boolean valid(String rest, long num1, long num2){

        if (rest.equals("")) return true;

        long sum = num1 + num2;
        String temp = ((Long)sum).toString();
        if (!rest.startsWith(temp)) return false;

        return valid(rest.substring(temp.length()), num2, sum);
    }
}