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.

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

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

class Solution {
    public boolean isAdditiveNumber(String num) {
        return helper(new ArrayList<Long>(), 0, num);
    }

    public boolean helper(List<Long> res, int start, String s) {
        if(start == s.length()) {
            if(res.size() >= 3){
                return true;
            } else {
                return false;
            }
        }

        for(int i = start + 1; i <= s.length(); i++) {
            String part = s.substring(start, i);

            if(isValidNumber(part)) {
                double num = Double.parseDouble(part);
                if(num > Long.MAX_VALUE)
                    return false;

                long n = Long.parseLong(part);
                if(res.size() < 2) {
                    res.add(n);
                    if(helper(res, i, s))
                        return true;
                    res.remove(res.size() - 1);
                } else {
                    if(res.get(res.size() - 2) + res.get(res.size() - 1) != n)
                        continue;

                    res.add(n);
                    if(helper(res, i, s))
                        return true;
                    res.remove(res.size() - 1);
                }
            }
        }
        return false;
    }

    public boolean isValidNumber(String s) {
        if(s.charAt(0) == '0' && s.length() > 1)
            return false;
        return true;
    }
}