Given a stringS of digits, such asS = "123456579", we can split it into aFibonacci-like sequence[123, 456, 579].

Formally, a Fibonacci-like sequence is a list Fof non-negative integers such that:

• 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
• F.length >= 3;
• andF[i] + F[i+1] = F[i+2]for all0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split fromS, or return[]if it cannot be done.

大体思路就是backtracking，但是有一些值得注意的小地方，一个是要检查截取的字符串是不是一个合法整数，比如‘01’这种就不合法，还有就是不能超过Integer.MAX_VALUE，可以把这个字符串parse成long类型然后比较。

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> res = new ArrayList<>();
        helper(res, 0, S);

        return res;
    }

    public boolean helper(List<Integer> 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)) {
                long n = Long.parseLong(part);
                if(n > Integer.MAX_VALUE)
                    return false;
                if(res.size() < 2) {
                    res.add((int)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((int)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;
    }
}