package leetcode;

import java.util.List;

/**
 * https://leetcode.com/problems/split-array-into-fibonacci-sequence/
 */
public class Problem842 {
    public List<Integer> splitIntoFibonacci(String S) {
        // TODO
        return null;
    }

    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]
    }
}

@@ -12,16 +12,44 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0A
 import j
@@ -236,35 +236,1402 @@
     
-// TODO%0A        return null
+List%3CInteger%3E answer = new ArrayList%3C%3E();%0A        if (S.length() %3C 3) %7B%0A            return answer;%0A        %7D%0A        for (int i = 1; i %3C= S.length(); i++) %7B%0A            for (int j = i + 1; j %3C= S.length(); j++) %7B%0A                answer.add(Integer.valueOf(S.substring(0, i)));%0A                if (splitIntoFibonacci(S, 0, i, i, j, answer) && answer.size() %3E= 3) %7B%0A                    return answer;%0A                %7D else %7B%0A                    answer.clear();%0A                %7D%0A            %7D%0A        %7D%0A        return answer;%0A    %7D%0A%0A    private static boolean splitIntoFibonacci(String s, int i, int j, int k, int l, List%3CInteger%3E answer) %7B%0A        if (l == s.length()) %7B%0A            answer.add(Integer.valueOf(s.substring(k, l)));%0A            return true;%0A        %7D%0A        int int1 = Integer.parseInt(s.substring(i, j));%0A        int int2 = Integer.parseInt(s.substring(k, l));%0A        long sum = int1 + int2;%0A        if (sum %3E Integer.MAX_VALUE) %7B%0A            return false;%0A        %7D%0A        String sumStr = Long.toString(sum);%0A        boolean found = false;%0A        if (l + sumStr.length() %3C= s.length() && sumStr.equals(s.substring(l, l + sumStr.length()))) %7B%0A            answer.add(int2);%0A            found = splitIntoFibonacci(s, k, l, l, l + sumStr.length(), answer);%0A            if (!found) %7B%0A                answer.remove(answer.size() - 1);%0A            %7D%0A        %7D%0A        return found
 ;%0A  
@@ -1720,24 +1720,26 @@
 oblem842();%0A
+//
         Syst
@@ -1809,16 +1809,18 @@
 56,579%5D%0A
+//
         
@@ -1896,16 +1896,18 @@
 5,8,13%5D%0A
+//
         
@@ -1962,32 +1962,34 @@
 58130%22)); // %5B%5D%0A
+//
         System.o
@@ -2039,16 +2039,18 @@
 ; // %5B%5D%0A
+//
         
@@ -2122,16 +2122,222 @@
 1, 111%5D%0A
+//        System.out.println(prob.splitIntoFibonacci(%221%22)); // %5B%5D%0A//        System.out.println(prob.splitIntoFibonacci(%221%22)); // %5B%5D%0A        System.out.println(prob.splitIntoFibonacci(%2214748364721%22)); // %5B%5D%0A
     %7D%0A%7D%0A

Update problem 842