Additive Number

Additive number is a string whose digits can form 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.

For example:
"112358" is an additive number because 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
"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.

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

Code

public class Solution {
    public boolean isAdditiveNumber(String num) {
        int len = num.length();
        //i不可能大于len的一半，如果大于，那么剩下的数的长度已经比0到i要小了，不可能是0到i和另外一个数的和
        for (int i=1; i<=len/2; i++){
            //跳出条件：剩下的长度小于前连个数中长的那个，前两个数的长度分别为i和j
            for (int j=1; Math.max(i,j) <= len-i-j;j++){
                if (isValid(i,j,num)) {return true;}
            }
        }
        return false;
    }

    private boolean isValid(int i, int j, String num){
        //检查第一个数不能是0开头，或者如果是0开头，只能是个位数
        if (num.charAt(0)=='0' && i>1) return false;
        //检查第二个数不能是0开头，或者如果是0开头，只能是个位数
        if (num.charAt(i)=='0' && j>1) return false;
        BigInteger x1 = new BigInteger(num.substring(0,i));
        BigInteger x2 = new BigInteger(num.substring(i,j));
        String sum;
        for (int start = i+j; start<num.length();start += sum.length()){
            x2 = x2.add(x1);
            x1 = x2.subtract(x1);
            sum = x2.toString();
            if (!num.startsWith(sum, start)) return false;
        }
        return true;
    }
}

Reference

Leetcode