842. Split Array into Fibonacci Sequence(#1 ).java

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> res = new ArrayList<>();
        int len = S.length();
        for (int i = 1; i < len && i < 11; i++) {
            if (S.charAt(0) == '0' && i > 1) return res;
            for (int j = 1; j < len - i && j < 11; j++) {
                if (S.charAt(i) == '0' && j > 1) continue;
                long a = Long.valueOf(S.substring(0, i));
                long b = Long.valueOf(S.substring(i, i + j));
                res.add((int)a);
                res.add((int)b);
                if (isFibonacci(S, a, b, i + j, res)) {
                    return res;
                }
                res.clear();
            }
        }
        return res;
    }
    
    private boolean isFibonacci(String S, long a, long b, int idx, List<Integer> res) {
        
        long sum = a + b;
        if (a + b > Integer.MAX_VALUE) return false;
        String sumStr = String.valueOf(sum);
        if (S.startsWith(sumStr, idx)) {
            res.add((int)sum);
            if (idx + sumStr.length() == S.length()) return true;
            return isFibonacci(S, b, sum, idx + sumStr.length(), res);
        }
        return false;
    }
}