1
class Solution {
2
 public:
3
  vector<int> ans;
4

5
  bool getFibo(string &s, int i, long a, long b, int n) {
6
    if (i == s.length()) return n > 2;
7

8
    long num = 0;
9
    for (int x = i; x < s.length(); x++) {
10
      num = num * 10 + s[x] - '0';
11
      if (num > INT_MAX) break;
12

13
      bool chk = false;
14
      ans.push_back(num);
15
      if (n < 2)
16
        chk = getFibo(s, x + 1, b, num, n + 1);
17
      else if (a + b == num)
18
        chk = getFibo(s, x + 1, b, num, n + 1);
19
      if (chk) return true;
20
      ans.pop_back();
21

22
      if (num == 0) break;
23
    }
24
    return false;
25
  }
26

27
  vector<int> splitIntoFibonacci(string S) {
28
    ans.clear();
29
    getFibo(S, 0, 0, 0, 0);
30
    return ans;
31
  }
32
};