Problem Description

Given a string num containing only digits, the task is to split it into a sequence of integers to form a Fibonacci-like sequence. A Fibonacci-like sequence is a list of numbers where each number is the sum of the two preceding ones (i.e., F[i] = F[i-1] + F[i-2] for all i >= 2).

The requirements are:

• Each number in the sequence must be a non-negative integer and fit within a 32-bit signed integer (<= 2^31 - 1).
• Numbers in the sequence cannot have leading zeros unless the number itself is 0.
• The sequence must have at least 3 numbers.
• All digits in num must be used, and no digit can be reused or left over.
• If there are multiple valid solutions, return any one of them. If no valid sequence exists, return an empty list.

Thought Process

At first glance, the problem seems to be about splitting the string in all possible ways and checking if any sequence forms a Fibonacci-like sequence. This hints at a brute-force or backtracking approach, since there are many ways to split the string.

However, we quickly realize that:

• We need to try all possible splits for the first and second numbers, and see if the rest of the string can be partitioned accordingly.
• Once the first two numbers are chosen, the rest of the sequence is determined: each next number must be the sum of the previous two, and we must check if the next part of the string matches that number.
• We must be careful with leading zeros and integer overflow.

Solution Approach

The solution can be broken down into the following steps:

1. Iterate over possible splits for the first two numbers:
   • Try all possible lengths for the first number (from 1 up to 10 digits, since 2³¹-1 has 10 digits).
   • For each first number, try all possible lengths for the second number (similarly constrained).
2. For each pair of first and second numbers:
   • Check for leading zeros and integer overflow.
   • Start building the sequence: repeatedly sum the last two numbers and check if the next part of the string matches.
   • If at any point the next number does not match, break and try the next split.
   • If all digits are used and the sequence has at least 3 numbers, return the sequence.
3. Return an empty list if no valid sequence is found.

This approach is efficient because:

• We only attempt to split the string for the first two numbers (a manageable number of possibilities).
• After that, the sequence is uniquely determined.
• We avoid unnecessary recursion by greedily matching the next required number.

Example Walkthrough

Let's consider the input num = "11235813".

1. Try first number 1 (index 0), second number 1 (index 1).
2. Next expected number: 2. The next digit is 2 (index 2) — matches.
3. Next expected: 3. Next digit is 3 (index 3) — matches.
4. Next expected: 5. Next digit is 5 (index 4) — matches.
5. Next expected: 8. Next digit is 8 (index 5) — matches.
6. Next expected: 13. Next two digits are 1 and 3 (index 6-7) — matches.
7. All digits used, sequence is [1, 1, 2, 3, 5, 8, 13]. Valid!

If at any point the next number does not match the corresponding substring, we backtrack and try a different split for the first or second number.

Time and Space Complexity

Brute-force approach:

• Would try all possible ways to split the string, leading to exponential time complexity in the length of num.

• We try up to 10 possible lengths for the first number, and up to 10 for the second (since 2³¹-1 has 10 digits).
• For each such pair, we scan the rest of the string linearly.
• So, the time complexity is O(L²), where L is the length of num.
• Space complexity is O(L) for storing the sequence.

This is efficient for reasonable input sizes.

Summary

The key insight is that once the first two numbers are chosen, the rest of the Fibonacci sequence is uniquely determined. By systematically trying all possible splits for the first two numbers and greedily checking the rest, we can efficiently find (or rule out) a valid sequence. The solution is elegant because it leverages the deterministic nature of the Fibonacci sequence and avoids unnecessary recursion or brute-force exploration.

Code Implementation

class Solution:
    def splitIntoFibonacci(self, S: str):
        n = len(S)
        for i in range(1, min(10, n)):
            if S[0] == '0' and i > 1:
                break
            a = int(S[:i])
            if a > 2**31 - 1:
                break
            for j in range(i+1, min(i+10, n)):
                if S[i] == '0' and j - i > 1:
                    break
                b = int(S[i:j])
                if b > 2**31 - 1:
                    break
                fib = [a, b]
                k = j
                while k < n:
                    nxt = fib[-1] + fib[-2]
                    if nxt > 2**31 - 1:
                        break
                    nxt_str = str(nxt)
                    if not S.startswith(nxt_str, k):
                        break
                    fib.append(nxt)
                    k += len(nxt_str)
                if k == n and len(fib) >= 3:
                    return fib
        return []
      

class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        int n = S.size();
        for (int i = 1; i < min(10, n); ++i) {
            if (S[0] == '0' && i > 1) break;
            long a = stol(S.substr(0, i));
            if (a > INT_MAX) break;
            for (int j = i+1; j < min(i+10, n); ++j) {
                if (S[i] == '0' && j - i > 1) break;
                long b = stol(S.substr(i, j-i));
                if (b > INT_MAX) break;
                vector<int> fib = { (int)a, (int)b };
                int k = j;
                while (k < n) {
                    long nxt = (long)fib[fib.size()-1] + fib[fib.size()-2];
                    if (nxt > INT_MAX) break;
                    string nxt_str = to_string(nxt);
                    if (S.substr(k, nxt_str.size()) != nxt_str) break;
                    fib.push_back((int)nxt);
                    k += nxt_str.size();
                }
                if (k == n && fib.size() >= 3) return fib;
            }
        }
        return {};
    }
};
      

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        int n = S.length();
        for (int i = 1; i < Math.min(10, n); i++) {
            if (S.charAt(0) == '0' && i > 1) break;
            long a = Long.parseLong(S.substring(0, i));
            if (a > Integer.MAX_VALUE) break;
            for (int j = i+1; j < Math.min(i+10, n); j++) {
                if (S.charAt(i) == '0' && j - i > 1) break;
                long b = Long.parseLong(S.substring(i, j));
                if (b > Integer.MAX_VALUE) break;
                List<Integer> fib = new ArrayList<>();
                fib.add((int)a);
                fib.add((int)b);
                int k = j;
                while (k < n) {
                    long nxt = (long)fib.get(fib.size()-1) + fib.get(fib.size()-2);
                    if (nxt > Integer.MAX_VALUE) break;
                    String nxtStr = String.valueOf(nxt);
                    if (!S.startsWith(nxtStr, k)) break;
                    fib.add((int)nxt);
                    k += nxtStr.length();
                }
                if (k == n && fib.size() >= 3) return fib;
            }
        }
        return new ArrayList<>();
    }
}
      

var splitIntoFibonacci = function(S) {
    const n = S.length;
    for (let i = 1; i < Math.min(10, n); i++) {
        if (S[0] === '0' && i > 1) break;
        let a = Number(S.slice(0, i));
        if (a > 2**31 - 1) break;
        for (let j = i+1; j < Math.min(i+10, n); j++) {
            if (S[i] === '0' && j - i > 1) break;
            let b = Number(S.slice(i, j));
            if (b > 2**31 - 1) break;
            let fib = [a, b];
            let k = j;
            while (k < n) {
                let nxt = fib[fib.length-1] + fib[fib.length-2];
                if (nxt > 2**31 - 1) break;
                let nxtStr = nxt.toString();
                if (S.slice(k, k + nxtStr.length) !== nxtStr) break;
                fib.push(nxt);
                k += nxtStr.length;
            }
            if (k === n && fib.length >= 3) return fib;
        }
    }
    return [];
};