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 ;
• and F[i] + F[i+1] = F[i+2] for all 0 < = 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.

Example 1:

Input: 
"123456579"

Output: 
[123,456,579]

Example 2:

Input: 
"11235813"

Output: 
[1,1,2,3,5,8,13]

Example 3:

Input: 
"112358130"

Output: 
[]

Explanation: 
The task is impossible.

Example 4:

Input: 
"0123"

Output: 
[]

Explanation: 
Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input: 
"1101111"

Output: 
[110, 1, 111]

Explanation: 
The output [11, 0, 11, 11] would also be accepted.

Note:

1. 1 < = S.length < = 200
2. S contains only digits.

class Solution {
    int max = Integer.MAX_VALUE;
    public List<Integer> splitIntoFibonacci(String S) {

        List<Integer> res = new ArrayList<>();
        for (int d = 1; d < S.length(); d++) {
            if (S.charAt(0) == '0' && d > 1) break;
            long num1 = Long.parseLong(S.substring(0, d));
            if (num1 > max) break;

            // add the first value
            res.add((int)num1);
            for (int i = d; i < S.length(); i++) {
                if (S.charAt(d) == '0' && i > d) break;
                long num2 = Long.parseLong(S.substring(d, i+1));
                if (num2 > max) break;

                //add the second value
                res.add((int)num2);
                if (dfs(S, i+1, (int)num1, (int)num2, res)) {
                    return res;
                }

                res.remove(1);
            }
            res.remove(0);
        }
        return res;
    }

    private boolean dfs(String s, int k, int num1, int num2, List<Integer> res) {
        if (k == s.length()) {
            if (res.size() > 2)
                return true;
            else 
                return false;
        }

        for (int i = k; i < s.length(); i++) {

            if (s.charAt(k) == '0' && i > k) break;
            long tmp = Long.parseLong(s.substring(k, i+1));
            if (tmp > max) return false;

            // value equals the sum of last two valus
            if (tmp == num1+num2) {
                res.add((int)tmp);
                if (dfs(s, i+1, (int)num2, (int)tmp, res)) return true;
                res.remove(res.size()-1);
            } else if (tmp > num1+num2) return false;
        }
        return false;
    }
}