LeetCode 842: Split Array into Fibonacci Sequence

Problem Restatement

We are given a string num containing only digits.

We need to split it into a Fibonacci-like sequence.

A valid Fibonacci-like sequence must satisfy these rules:

Return any valid sequence.

If no valid sequence exists, return an empty list. The official statement gives examples such as "123456579" -> [123, 456, 579], and notes that every value must be between 0 and 2^31 - 1.

Input and Output

Function shape:

class Solution:
    def splitIntoFibonacci(self, num: str) -> list[int]:
        ...

Examples

Example 1:

num = "123456579"

We can split it as:

[123, 456, 579]

because:

123 + 456 = 579

So the answer can be:

[123, 456, 579]

Example 2:

num = "11235813"

We can split it as:

[1, 1, 2, 3, 5, 8, 13]

Each number is the sum of the previous two.

Example 3:

num = "112358130"

There is no valid split.

So the answer is:

[]

Example 4:

num = "0123"

We cannot use "01" as a number because leading zeroes are not allowed.

So the answer is:

[]

First Thought: Try Every Split

The string can be cut into many possible numbers.

For example:

"123456579"

could start as:

1, ...
12, ...
123, ...
1234, ...

Once we pick the first two numbers, the rest of the sequence is almost fixed. The next number must be their sum.

So a natural approach is backtracking:

1. Try a number starting at the current index.
2. Check whether it is valid.
3. If the sequence has at least two numbers, check whether the new number equals the sum of the previous two.
4. Continue recursively.
5. Backtrack if the path fails.

Key Insight

At any point, if the current sequence already has two numbers, the next number has only one possible value:

seq[-2] + seq[-1]

So we can prune early.

When building a candidate number from the string:

This makes the search much smaller than trying all partitions blindly.

Algorithm

Use DFS with a path list seq.

At index start:

1. If start == len(num):

   1. Return True if len(seq) >= 3.
   2. Otherwise return False.

2. Build the next number by trying each end index from start to the end of the string.

3. If num[start] == "0" and the number has more than one digit, stop.

4. Convert the substring to an integer.

5. If the value exceeds 2^31 - 1, stop.

6. If len(seq) >= 2:

   1. Let expected = seq[-2] + seq[-1].
   2. If value < expected, continue.
   3. If value > expected, stop.
   4. If equal, use it.

7. Add the value to seq.

8. Recurse from the next index.

9. If recursion succeeds, return True.

10. Otherwise remove the value and try another split.

If no branch works, return False.

Walkthrough

Use:

num = "11235813"

Start with an empty sequence:

seq = []

Choose first number:

1

Now:

seq = [1]

Choose second number:

1

Now:

seq = [1, 1]

The next expected number is:

1 + 1 = 2

The next digit is "2", so add it:

seq = [1, 1, 2]

Next expected:

1 + 2 = 3

Add 3:

seq = [1, 1, 2, 3]

Next expected:

2 + 3 = 5

Add 5:

seq = [1, 1, 2, 3, 5]

Next expected:

3 + 5 = 8

Add 8:

seq = [1, 1, 2, 3, 5, 8]

Next expected:

5 + 8 = 13

The remaining string is "13", so add it:

seq = [1, 1, 2, 3, 5, 8, 13]

Now all digits are used and the sequence length is at least 3.

Return this sequence.

Correctness

The DFS tries every possible valid substring starting at the current index, subject to the problem’s constraints.

It rejects numbers with extra leading zeroes, so every number it adds to seq has a valid decimal representation.

It rejects numbers larger than 2^31 - 1, so every number it adds satisfies the 32-bit signed integer limit.

When seq has fewer than two numbers, any valid number can be chosen because the Fibonacci rule has not started yet.

When seq has at least two numbers, the next number must equal seq[-2] + seq[-1]. The DFS only accepts the candidate number when it equals that sum. Therefore, every completed sequence returned by the algorithm satisfies the Fibonacci rule.

The DFS explores all possible choices for the first number, second number, and every later valid continuation. If a valid split exists, its first number appears among the tried prefixes, its second number appears among the tried prefixes after that, and every later number is accepted because it equals the required sum. So the DFS will find it.

If the DFS finishes without success, then every valid partition has been rejected for a real constraint violation or a Fibonacci mismatch. Therefore, no valid sequence exists.

Complexity

Let:

n = len(num)

The 32-bit limit also bounds candidate number length to at most 10 digits, which keeps branching small.

Implementation

class Solution:
    def splitIntoFibonacci(self, num: str) -> list[int]:
        limit = 2**31 - 1
        seq = []

        def dfs(start: int) -> bool:
            if start == len(num):
                return len(seq) >= 3

            value = 0

            for end in range(start, len(num)):
                if end > start and num[start] == "0":
                    break

                value = value * 10 + int(num[end])

                if value > limit:
                    break

                if len(seq) >= 2:
                    expected = seq[-2] + seq[-1]

                    if value < expected:
                        continue

                    if value > expected:
                        break

                seq.append(value)

                if dfs(end + 1):
                    return True

                seq.pop()

            return False

        dfs(0)
        return seq

Code Explanation

The maximum allowed value is:

limit = 2**31 - 1

The current candidate sequence is stored in:

seq = []

The DFS starts at an index in the string:

def dfs(start: int) -> bool:

If all digits are used, the split is valid only if it has at least three numbers:

if start == len(num):
    return len(seq) >= 3

We build the next number digit by digit:

value = value * 10 + int(num[end])

Leading zeroes are rejected:

if end > start and num[start] == "0":
    break

For example, "0" is allowed, but "01" is not.

The 32-bit limit is enforced here:

if value > limit:
    break

If there are already two numbers, the next value must match the Fibonacci sum:

expected = seq[-2] + seq[-1]

If the current value is too small, we need more digits:

if value < expected:
    continue

If it is too large, extending it will only make it larger, so this branch can stop:

if value > expected:
    break

When the value is acceptable, add it:

seq.append(value)

If the recursive call succeeds, return immediately:

if dfs(end + 1):
    return True

Otherwise, undo the choice:

seq.pop()

Finally, the public function returns the found sequence, or [] if none was found.

Testing

def run_tests():
    s = Solution()

    assert s.splitIntoFibonacci("123456579") == [123, 456, 579]
    assert s.splitIntoFibonacci("11235813") == [1, 1, 2, 3, 5, 8, 13]
    assert s.splitIntoFibonacci("112358130") == []
    assert s.splitIntoFibonacci("0123") == []
    assert s.splitIntoFibonacci("1101111") in ([110, 1, 111], [11, 0, 11, 11])
    assert s.splitIntoFibonacci("0000") == [0, 0, 0, 0]
    assert s.splitIntoFibonacci("214748364721474836422147483641") == []

    print("all tests passed")

run_tests()

Test meaning: