# 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:

| Rule | Meaning |
|---|---|
| Length | The sequence must contain at least `3` numbers |
| Value limit | Every number must fit in a 32-bit signed integer |
| Fibonacci rule | `seq[i] + seq[i + 1] == seq[i + 2]` |
| Leading zero rule | A number cannot have extra leading zeroes |

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

| Item | Meaning |
|---|---|
| Input | A digit string `num` |
| Output | A list of integers forming a Fibonacci-like sequence |
| Failure case | Return `[]` |
| Minimum sequence length | `3` |
| Maximum integer | `2^31 - 1` |

Function shape:

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

## Examples

Example 1:

```python
num = "123456579"
```

We can split it as:

```python
[123, 456, 579]
```

because:

```python
123 + 456 = 579
```

So the answer can be:

```python
[123, 456, 579]
```

Example 2:

```python
num = "11235813"
```

We can split it as:

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

Each number is the sum of the previous two.

Example 3:

```python
num = "112358130"
```

There is no valid split.

So the answer is:

```python
[]
```

Example 4:

```python
num = "0123"
```

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

So the answer is:

```python
[]
```

## First Thought: Try Every Split

The string can be cut into many possible numbers.

For example:

```python
"123456579"
```

could start as:

```python
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:

```python
seq[-2] + seq[-1]
```

So we can prune early.

When building a candidate number from the string:

| Invalid case | Action |
|---|---|
| It has a leading zero | Stop extending this number |
| It exceeds `2^31 - 1` | Stop extending this number |
| It is greater than expected Fibonacci sum | Stop this branch |
| It is less than expected Fibonacci sum | Try extending with one more digit |

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:

```python
num = "11235813"
```

Start with an empty sequence:

```python
seq = []
```

Choose first number:

```python
1
```

Now:

```python
seq = [1]
```

Choose second number:

```python
1
```

Now:

```python
seq = [1, 1]
```

The next expected number is:

```python
1 + 1 = 2
```

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

```python
seq = [1, 1, 2]
```

Next expected:

```python
1 + 2 = 3
```

Add `3`:

```python
seq = [1, 1, 2, 3]
```

Next expected:

```python
2 + 3 = 5
```

Add `5`:

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

Next expected:

```python
3 + 5 = 8
```

Add `8`:

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

Next expected:

```python
5 + 8 = 13
```

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

```python
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:

```python
n = len(num)
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` in practice | The main choices are the first two numbers; later values are forced |
| Space | `O(n)` | Recursion path can contain up to `n` one-digit numbers |

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

## Implementation

```python
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:

```python
limit = 2**31 - 1
```

The current candidate sequence is stored in:

```python
seq = []
```

The DFS starts at an index in the string:

```python
def dfs(start: int) -> bool:
```

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

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

We build the next number digit by digit:

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

Leading zeroes are rejected:

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

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

The 32-bit limit is enforced here:

```python
if value > limit:
    break
```

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

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

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

```python
if value < expected:
    continue
```

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

```python
if value > expected:
    break
```

When the value is acceptable, add it:

```python
seq.append(value)
```

If the recursive call succeeds, return immediately:

```python
if dfs(end + 1):
    return True
```

Otherwise, undo the choice:

```python
seq.pop()
```

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

## Testing

```python
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:

| Test | Why |
|---|---|
| `"123456579"` | Confirms multi-digit Fibonacci split |
| `"11235813"` | Confirms classic Fibonacci sequence |
| `"112358130"` | Confirms invalid suffix returns empty |
| `"0123"` | Confirms leading zero rule |
| `"1101111"` | Confirms multiple valid outputs may exist |
| `"0000"` | Confirms zero is valid as a single digit |
| Large values | Confirms 32-bit integer limit |