1def splitIntoFibonacci(S):
2    def backtrack(index):
3        if index == len(S):
4            return len(result) >= 3
5        current_number = 0
6        for i in range(index, len(S)):
7            if i > index and S[index] == '0':
8                break
9            current_number = current_number * 10 + int(S[i])
10            if current_number > 2**31 - 1:
11                break
12            if len(result) < 2 or current_number == result[-1] + result[-2]:
13                result.append(current_number)
14                if backtrack(i + 1):
15                    return True
16                result.pop()
17        return False
18
19    result = []
20    return result if backtrack(0) else []

1using System;
2using System.Collections.Generic;
3
4public class Solution {
    public IList<int> SplitIntoFibonacci(string S) {
        var result = new List<int>();
        for (int i = 0; i < S.Length - 2; i++) {
            if (i > 0 && S[0] == '0') break;
            long a = long.Parse(S.Substring(0, i + 1));
            if (a > int.MaxValue) break;
            result.Add((int)a);
            for (int j = i + 1; j < S.Length - 1; j++) {
                if (j > i + 1 && S[i + 1] == '0') break;
                long b = long.Parse(S.Substring(i + 1, j + 1 - (i + 1)));
                if (b > int.MaxValue) break;
                result.Add((int)b);
                if (IsValid(S.Substring(j + 1), result)) return result;
                result.RemoveAt(result.Count - 1);
            }
            result.RemoveAt(result.Count - 1);
        }
        return new List<int>();
    }

    private bool IsValid(string S, List<int> result) {
        int n1 = result[result.Count - 2];
        int n2 = result[result.Count - 1];
        for (int k = 0; k < S.Length; k++) {
            long next = (long)n1 + n2;
            if (next > int.MaxValue) return false;
            string nextString = next.ToString();
            if (!S.StartsWith(nextString)) return false;
            n1 = n2;
            n2 = (int)next;
            k += nextString.Length - 1;
        }
        return true;
    }
}