1
class Solution {
2
  List<Integer> list = new ArrayList<>();
3

4
  public List<Integer> splitIntoFibonacci(String num) {
5

6
    if (backtrack(num, 0)) return list;
7
    else return new ArrayList();
8
  }
9

10
  boolean backtrack(String num, int index) {
11
    if (index == num.length()) return list.size() > 2;
12

13
    int n = 0;
14
    for (int i = index; i < num.length(); i++) {
15
      n = n * 10 + (num.charAt(i) - '0');
16
      if (n < 0) return false;
17
      if (list.size() < 2 || list.get(list.size() - 1) + list.get(list.size() - 2) == n) {
18
        list.add(n);
19
        if (backtrack(num, i + 1)) return true;
20
        list.remove(list.size() - 1);
21
      }
22

23
      if (i == index && num.charAt(i) == '0') return false;
24
    }
25
    return false;
26
  }
27
}