> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Split Array into Fibonacci Sequence

> Tested Python solution for LeetCode 842 with 24 pytest cases. Generate a practice environment with lcpy.

LeetCode 842, [Medium](/catalog/medium). Topics: [String](/catalog/topics/string), [Backtracking](/catalog/topics/backtracking). [View on LeetCode](https://leetcode.com/problems/split-into-fibonacci-sequence/description/).

Generate this problem as a practice environment: tested reference solution, 24 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 842   # by problem number
lcpy gen -s split_into_fibonacci_sequence   # by problem name
```

## Problem

You are given a string of digits `num`, such as `"123456579"`. We can split it into a Fibonacci-like sequence `[123, 456, 579]`.

Formally, a **Fibonacci-like** sequence is a list `f` of non-negative integers such that:

* `0 <= f[i] < 2^31`, (that is, each integer fits in a **32-bit** signed integer type),
* `f.length >= 3`, and
* `f[i] + f[i + 1] == f[i + 2]` for all `0 <= i < f.length - 2`.

Note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number `0` itself.

Return any Fibonacci-like sequence split from `num`, or return `[]` if it cannot be done.

### Examples

```
Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.
```

```
Input: num = "112358130"
Output: []
Explanation: The task is impossible.
```

```
Input: num = "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.
```

### Constraints

* `1 <= num.length <= 200`
* `num` contains only digits.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/split_into_fibonacci_sequence/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/split_into_fibonacci_sequence/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(10^2 * n) piece starts are bounded by 10 digits each
    # Space: O(n) for the sequence and recursion
    def split_into_fibonacci(self, num: str) -> list[int]:
        limit = 2**31
        n = len(num)

        for i in range(1, min(n, 10) + 1):
            if num[0] == "0" and i > 1:
                break
            first = int(num[:i])
            if first >= limit:
                break
            for j in range(1, min(n - i, 10) + 1):
                if num[i] == "0" and j > 1:
                    break
                second = int(num[i : i + j])
                if second >= limit:
                    break
                seq = [first, second]
                k = i + j
                while k < n:
                    nxt = seq[-1] + seq[-2]
                    if nxt >= limit or not num.startswith(str(nxt), k):
                        break
                    seq.append(nxt)
                    k += len(str(nxt))
                if k == n and len(seq) >= 3:
                    return seq
        return []
```

## Complexity

| Time | Space |
| - | - |
| O(10^2 \* n) piece starts are bounded by 10 digits each | O(n) for the sequence and recursion |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.