# Split Array into Fibonacci Sequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/split-array-into-fibonacci-sequence)
Canonical: https://scaleengineer.com/dsa/problems/split-array-into-fibonacci-sequence
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** String
---
## 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] < 231`, (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.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

**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.

# Approaches
## Brute Force by Generating All Partitions
This approach involves generating every single possible way to split the input string `num` into a sequence of numbers. For each generated sequence (partition), it then checks if that sequence adheres to the rules of a Fibonacci-like sequence. This is a straightforward but highly inefficient method.
**Time:** O(2^n * n). There are `2^(n-1)` possible ways to partition a string of length `n`. For each partition, we need to validate it, which involves iterating through its elements, parsing them, and checking the Fibonacci property. This validation takes O(n) time. The total time complexity is therefore exponential, making it impractical for the given constraints. · **Space:** O(2^n * n). If we store all partitions before validation, the space required is exponential. If we validate partitions as they are generated, the space complexity is determined by the recursion depth, which is O(n).
**Pros:** Simple to understand and conceptualize.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The brute-force method systematically explores all partitions of the input string. A partition is a list of substrings that, when concatenated, form the original string. We can imagine placing dividers in the `n-1` spaces between the characters of the string. Each combination of dividers creates a unique partition.

We can implement this using a recursive helper function. This function would build a partition piece by piece. For each valid partition found, we would then perform a separate validation step to check if it's a Fibonacci-like sequence. This validation involves checking the number of elements, leading zeros, integer range, and the sum property.

The first partition that passes this validation is returned. If we exhaust all `2^(n-1)` partitions without finding a valid one, we conclude that it's impossible and return an empty list.
### Algorithm
*   Define a recursive function, say `generatePartitions(index, currentPartition)`, to generate all possible ways to split the string `num`.
*   The base case for the recursion is when `index` reaches the end of the string. At this point, a complete partition has been formed, so it's added to a list of all partitions.
*   The recursive step involves iterating from `i = index` to `n-1`. In each iteration, a new substring `num.substring(index, i + 1)` is considered as the next number in the partition. This number is added to the `currentPartition`, and the function is called recursively for the rest of the string starting from `i + 1`.
*   After the recursive call returns, backtrack by removing the last added number to explore other possibilities.
*   Once all `2^(n-1)` partitions are generated, iterate through each one.
*   For each partition, validate it by checking:
    1.  It has at least three numbers.
    2.  No number has an invalid leading zero (e.g., "01").
    3.  All numbers parse to a value less than or equal to `Integer.MAX_VALUE`.
    4.  The Fibonacci property `f[i] + f[i+1] == f[i+2]` holds true for all applicable `i`.
*   The first partition that satisfies all these conditions is the answer. If no such partition is found after checking all of them, the answer is an empty list.

## Backtracking with Pruning
A more optimized approach is to use backtracking with pruning. Instead of generating all possible partitions and then validating them, we build a potential Fibonacci-like sequence number by number. At each step, we check if the sequence is still valid. If it violates the Fibonacci property or other constraints, we immediately abandon that path (prune the search tree). This avoids a massive amount of unnecessary computation.
**Time:** O(L^2 * N), which is effectively O(N). Here, N is the length of the input string and L is the maximum number of digits for a 32-bit integer (approximately 10). The algorithm's runtime is dominated by the process of selecting the first two numbers. Due to the `Integer.MAX_VALUE` constraint, any valid number in the sequence can have a length of at most L. Thus, there are `O(min(N, L)^2)` choices for the first two numbers. For each choice, we verify if the rest of the string matches the generated Fibonacci sequence, which takes O(N) time. Since L is a small constant, the complexity is effectively linear in N. In the worst-case without the value constraint (or for small N), the complexity would be closer to O(N^3). · **Space:** O(N). The space is used by the recursion call stack and the `result` list. The maximum depth of the recursion is N (if all numbers are single-digit), and the result list can also hold up to N numbers. Thus, the space complexity is linear with respect to the input string length.
**Pros:** Highly efficient due to aggressive pruning of the search space.; Guaranteed to find a solution if one exists.; Relatively straightforward to implement using recursion.
**Cons:** The recursive nature can lead to stack overflow on extremely large inputs, though not an issue for the given constraints.; The time complexity analysis is nuanced, though it performs very well in practice.
### Explanation
This method uses a depth-first search (DFS) to explore possible partitions. The search is guided by the constraints of the problem, which allows for aggressive pruning of the search space.

The main idea is that a Fibonacci sequence is fully determined by its first two numbers. Our backtracking function tries to establish these first two numbers, and then verifies if the rest of the string follows the sequence.

The function attempts to parse a number from the current index. It checks for leading zeros and integer overflow. If the number is valid, it checks if it can be appended to the current sequence. If the sequence has fewer than two numbers, any valid number can be added. If it has two or more, the new number must be the sum of the last two. If the current number becomes larger than the required sum, we know that any longer number starting from the same index will also be too large, so we can stop searching along this path. This pruning is key to the efficiency of the algorithm.

If a valid number is found, it's added to our result list, and we recurse on the rest of the string. If the recursive call doesn't lead to a solution, we backtrack by removing the number and trying a different, longer number from the original index.

```java
class Solution {
    public List<Integer> splitIntoFibonacci(String num) {
        List<Integer> result = new ArrayList<>();
        backtrack(num, 0, result);
        return result;
    }

    private boolean backtrack(String num, int index, List<Integer> result) {
        if (index == num.length()) {
            return result.size() >= 3;
        }

        long currentNum = 0;
        for (int i = index; i < num.length(); i++) {
            // Rule: no extra leading zeroes, except for the number 0 itself.
            if (num.charAt(index) == '0' && i > index) {
                break;
            }

            currentNum = currentNum * 10 + (num.charAt(i) - '0');
            
            // Rule: each integer fits in a 32-bit signed integer type.
            if (currentNum > Integer.MAX_VALUE) {
                break;
            }

            int size = result.size();
            // If we are picking the first two numbers, or if the current number
            // matches the sum of the previous two.
            if (size < 2 || currentNum == (long)result.get(size - 1) + result.get(size - 2)) {
                result.add((int) currentNum);
                // Recurse to check the rest of the string.
                if (backtrack(num, i + 1, result)) {
                    return true;
                }
                // Backtrack if the recursive call did not find a solution.
                result.remove(result.size() - 1);
            }
            // Pruning: if the current number is already larger than the expected sum,
            // any longer number from this index will also be too large.
            else if (size >= 2 && currentNum > (long)result.get(size - 1) + result.get(size - 2)) {
                break;
            }
        }
        return false;
    }
}
```
### Algorithm
*   Define a backtracking function `backtrack(index, result)` where `index` is the current position in the string `num` and `result` is the list of numbers found so far.
*   **Base Case:** If `index` reaches the end of `num`, it means we've successfully partitioned the whole string. If `result.size() >= 3`, we've found a valid solution, so return `true`.
*   **Recursive Step:** Iterate with a loop variable `i` from `index` to `num.length() - 1` to define the end of the next potential number.
    *   Construct the current number candidate `currentNum` from the substring `num.substring(index, i + 1)`.
    *   **Validation and Pruning 1 (Leading Zeros):** If the substring starts with '0' and has length greater than 1, it's invalid. Break the loop, as any longer substring from `index` will also have a leading zero.
    *   **Validation and Pruning 2 (Integer Overflow):** Parse the substring. If its value exceeds `Integer.MAX_VALUE`, break the loop, as any longer substring will also be too large.
    *   Let `size = result.size()`. Check the Fibonacci property:
        *   If `size < 2`, any valid `currentNum` can be the first or second number. Add it to `result` and recurse: `backtrack(i + 1, result)`. If the call returns `true`, a solution is found, so propagate `true`.
        *   If `size >= 2`, `currentNum` must equal the sum of the last two numbers in `result`. Let `sum = result.get(size - 1) + result.get(size - 2)`.
            *   If `currentNum < sum`, the number is too small. Continue the loop to form a larger number.
            *   **Pruning 3:** If `currentNum > sum`, the number is too large. Since subsequent numbers from `index` will be even larger, this path is invalid. Break the loop.
            *   If `currentNum == sum`, it's a match. Add it to `result` and recurse: `backtrack(i + 1, result)`. If the call returns `true`, propagate `true`.
    *   If a recursive call returns `false`, backtrack by removing the number just added to `result` to explore other possibilities.
*   If the loop completes without finding a solution from `index`, return `false`.

# Solutions
### Java

```java
class Solution { private List < Integer > ans = new ArrayList <>(); private String num ; public List < Integer > splitIntoFibonacci ( String num ) { this . num = num ; dfs ( 0 ); return ans ; } private boolean dfs ( int i ) { if ( i == num . length ()) { return ans . size () >= 3 ; } long x = 0 ; for ( int j = i ; j < num . length (); ++ j ) { if ( j > i && num . charAt ( i ) == '0' ) { break ; } x = x * 10 + num . charAt ( j ) - '0' ; if ( x > Integer . MAX_VALUE || ( ans . size () >= 2 && x > ans . get ( ans . size () - 1 ) + ans . get ( ans . size () - 2 ))) { break ; } if ( ans . size () < 2 || x == ans . get ( ans . size () - 1 ) + ans . get ( ans . size () - 2 )) { ans . add (( int ) x ); if ( dfs ( j + 1 )) { return true ; } ans . remove ( ans . size () - 1 ); } } return false ; } }
```

### CPP

```cpp
class Solution { public: vector < int > splitIntoFibonacci ( string num ) { int n = num . size (); vector < int > ans ; function < bool ( int ) > dfs = [ & ]( int i ) -> bool { if ( i == n ) { return ans . size () > 2 ; } long long x = 0 ; for ( int j = i ; j < n ; ++ j ) { if ( j > i && num [ i ] == '0' ) { break ; } x = x * 10 + num [ j ] - '0' ; if ( x > INT_MAX || ( ans . size () > 1 && x > ( long long ) ans [ ans . size () - 1 ] + ans [ ans . size () - 2 ])) { break ; } if ( ans . size () < 2 || x == ( long long ) ans [ ans . size () - 1 ] + ans [ ans . size () - 2 ]) { ans . push_back ( x ); if ( dfs ( j + 1 )) { return true ; } ans . pop_back (); } } return false ; }; dfs ( 0 ); return ans ; } };
```

### Python

```python
class Solution : def splitIntoFibonacci ( self , num : str ) -> List [ int ]: def dfs ( i ): if i == n : return len ( ans ) > 2 x = 0 for j in range ( i , n ): if j > i and num [ i ] == '0' : break x = x * 10 + int ( num [ j ]) if x > 2 ** 31 - 1 or ( len ( ans ) > 2 and x > ans [ - 2 ] + ans [ - 1 ]): break if len ( ans ) < 2 or ans [ - 2 ] + ans [ - 1 ] == x : ans . append ( x ) if dfs ( j + 1 ): return True ans . pop () return False n = len ( num ) ans = [] dfs ( 0 ) return ans
```