package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/split-array-into-fibonacci-sequence/
 */
public class Problem842 {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> answer = new ArrayList<>();
        if (S.length() < 3) {
            return answer;
        }
        for (int i = 1; i <= S.length(); i++) {
            for (int j = i + 1; j <= S.length(); j++) {
                try {
                    answer.add(Integer.valueOf(S.substring(0, i)));
                    if (splitIntoFibonacci(S, 0, i, i, j, answer) && answer.size() >= 3) {
                        return answer;
                    } else {
                        answer.clear();
                    }
                } catch (NumberFormatException e) {
                    answer.clear();
                }
            }
        }
        return answer;
    }

    private static boolean splitIntoFibonacci(String s, int i, int j, int k, int l, List<Integer> answer) {
        if (l == s.length()) {
            answer.add(Integer.parseInt(s.substring(k, l)));
            return true;
        }
        int num1 = Integer.parseInt(s.substring(i, j));
        int num2 = Integer.parseInt(s.substring(k, l));
        long sum = num1 + num2;
        if (sum > Integer.MAX_VALUE) {
            return false;
        }
        String sumStr = Long.toString(sum);
        boolean found = false;
        if (l + sumStr.length() <= s.length() && sumStr.equals(s.substring(l, l + sumStr.length()))) {
            answer.add((int) num2);
            found = splitIntoFibonacci(s, k, l, l, l + sumStr.length(), answer);
            if (!found) {
                answer.remove(answer.size() - 1);
            }
        }
        return found;
    }

    public static void main(String[] args) {
        Problem842 prob = new Problem842();
//        System.out.println(prob.splitIntoFibonacci("123456579")); // [123,456,579]
//        System.out.println(prob.splitIntoFibonacci("11235813")); // [1,1,2,3,5,8,13]
//        System.out.println(prob.splitIntoFibonacci("112358130")); // []
//        System.out.println(prob.splitIntoFibonacci("0123")); // []
//        System.out.println(prob.splitIntoFibonacci("1101111")); // [110, 1, 111]
//        System.out.println(prob.splitIntoFibonacci("1")); // []
//        System.out.println(prob.splitIntoFibonacci("1")); // []
//        System.out.println(prob.splitIntoFibonacci("14748364721")); // []
//        System.out.println(prob.splitIntoFibonacci("214748364721474836422147483641")); // []
        System.out.println(prob.splitIntoFibonacci("0123")); // []
    }
}

@@ -1071,36 +1071,247 @@
     
-answer.add(Integer.parseInt(
+String sub = s.substring(k, l);%0A            if (sub.length() %3E 1 && sub.startsWith(%220%22)) %7B%0A                return false;%0A            %7D%0A            answer.add(Integer.parseInt(sub));%0A            return true;%0A        %7D%0A        String sub1 = 
 s.su
@@ -1322,16 +1322,71 @@
 ing(
-k, l)));
+i, j);%0A        if (sub1.length() %3E 1 && sub1.startsWith(%220%22)) %7B
 %0A   
@@ -1393,35 +1393,36 @@
          return 
-tru
+fals
 e;%0A        %7D%0A   
@@ -1446,32 +1446,61 @@
 nteger.parseInt(
+sub1);%0A        String sub2 = 
 s.substring(i, j
@@ -1499,15 +1499,107 @@
 ing(
-i, j));
+k, l);%0A        if (sub2.length() %3E 1 && sub2.startsWith(%220%22)) %7B%0A            return false;%0A        %7D
 %0A   
@@ -1632,32 +1632,19 @@
 rseInt(s
-.substring(k, l)
+ub2
 );%0A     
@@ -2258,18 +2258,16 @@
 m842();%0A
-//
         
@@ -2341,18 +2341,16 @@
 56,579%5D%0A
-//
         
@@ -2426,18 +2426,16 @@
 5,8,13%5D%0A
-//
         
@@ -2490,34 +2490,32 @@
 58130%22)); // %5B%5D%0A
-//
         System.o
@@ -2557,34 +2557,32 @@
 %220123%22)); // %5B%5D%0A
-//
         System.o
@@ -2646,18 +2646,16 @@
 1, 111%5D%0A
-//
         
@@ -2702,34 +2702,32 @@
 ci(%221%22)); // %5B%5D%0A
-//
         System.o
@@ -2766,34 +2766,32 @@
 ci(%221%22)); // %5B%5D%0A
-//
         System.o
@@ -2848,18 +2848,16 @@
 ; // %5B%5D%0A
-//
         

Update problem 842