LeetCode 842 - Split Array into Fibonacci Sequence
The problem gives us a string consisting only of digits, and asks us to split it into a sequence of integers that behaves like a Fibonacci sequence. A Fibonacci-like sequence follows three important rules: 1.
Difficulty: 🟡 Medium
Topics: String, Backtracking
Solution
LeetCode 842 - Split Array into Fibonacci Sequence
Problem Understanding
The problem gives us a string consisting only of digits, and asks us to split it into a sequence of integers that behaves like a Fibonacci sequence.
A Fibonacci-like sequence follows three important rules:
- Every number must fit inside a signed 32-bit integer, meaning each value must be less than
2^31. - The sequence must contain at least three numbers.
- Starting from the third number, every value must equal the sum of the previous two values.
For example, the sequence:
[123, 456, 579]
is valid because:
123 + 456 = 579
The challenge is that the input is given as a single string, so we must determine where to split it into numbers.
The problem also introduces an important restriction involving leading zeroes. A number like "0" is valid, but "01" or "00" is not valid as a multi-digit number. This means that once a substring begins with '0', the only valid number from that position is exactly 0.
The input size can be as large as 200 digits, which is far too large for brute force enumeration of every possible partition. However, the 32-bit integer constraint significantly limits the number of valid numeric candidates we actually need to consider. Since 2^31 - 1 has only 10 digits, each generated number can contain at most 10 digits.
Several edge cases are especially important:
- Strings beginning with zeroes, such as
"0123". - Cases where a valid sequence exists in multiple forms.
- Very large numbers that overflow 32-bit signed integer range.
- Inputs that almost form a Fibonacci sequence but fail late.
- Inputs too short to form a valid sequence.
The problem guarantees only that the input contains digits, nothing more.
Approaches
Brute Force Approach
The brute force idea is to try every possible way to split the string into substrings, convert each substring into an integer, and then check whether the resulting sequence satisfies Fibonacci rules.
Suppose the string has length n. Between every pair of characters, we may either split or not split. That produces roughly 2^(n-1) possible partitions.
For each partition:
- Convert all pieces into integers.
- Reject partitions with leading zeroes.
- Reject partitions with overflow.
- Check whether the Fibonacci property holds.
This approach is correct because it examines every possible partition, so if a valid sequence exists, it will eventually find it.
However, it is completely impractical for n = 200. The number of partitions grows exponentially.
Optimal Backtracking Approach
The key observation is that Fibonacci sequences are highly constrained.
Once we choose the first two numbers, every subsequent number is completely determined. There is no branching afterward because:
next = previous1 + previous2
Therefore, instead of trying arbitrary partitions everywhere, we only need to:
- Try all possibilities for the first number.
- Try all possibilities for the second number.
- Recursively verify whether the rest of the string matches the required sums.
This dramatically reduces the search space.
Another important optimization comes from the 32-bit integer limit. Since every valid number must fit inside signed 32-bit range, each number can contain at most 10 digits. This bounds the branching factor.
Backtracking works naturally here because:
- We build the sequence incrementally.
- We abandon invalid paths immediately.
- We stop as soon as we find one valid sequence.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Tries every possible partition |
| Optimal Backtracking | O(n^2) in practice | O(n) | First two numbers determine the rest |
Algorithm Walkthrough
- Initialize an empty sequence that will store the Fibonacci numbers we build during recursion.
- Use backtracking starting from index
0in the string. At each recursive call, attempt to extend the current sequence with a new number. - Build the current number digit by digit using substring expansion. This avoids generating all substrings ahead of time.
- If the current substring starts with
'0'and contains more than one digit, stop exploring further extensions from this position. This enforces the no-leading-zero rule. - Convert the substring into an integer. If the value exceeds
2^31 - 1, stop immediately because longer substrings will only become larger. - If the sequence already contains at least two numbers:
- Compute the expected next Fibonacci value:
expected = sequence[-1] + sequence[-2]
- If the current number is smaller than expected, continue extending the substring because we may need more digits.
- If the current number is larger than expected, stop exploring this branch because numbers only increase as we append digits.
- If the number matches the expected value, continue recursion.
- Append the valid number to the sequence and recurse using the next index in the string.
- If recursion succeeds and reaches the end of the string with at least three numbers, return success immediately.
- Otherwise, remove the last number from the sequence and continue exploring other possibilities.
- If all possibilities fail, return an empty list.
Why it works
The algorithm works because every valid Fibonacci decomposition must begin with some choice of first and second numbers. Once those are fixed, every remaining number is uniquely determined by the Fibonacci rule.
The backtracking process systematically explores all possible first and second numbers while pruning impossible branches early through:
- leading zero validation,
- overflow checks,
- Fibonacci sum comparisons.
Therefore, if a valid sequence exists, the algorithm will find it. If no valid sequence exists, all branches will eventually be rejected.
Python Solution
from typing import List
class Solution:
def splitIntoFibonacci(self, num: str) -> List[int]:
MAX_INT = 2**31 - 1
sequence = []
def backtrack(index: int) -> bool:
# Successfully consumed entire string
if index == len(num):
return len(sequence) >= 3
current_number = 0
for end in range(index, len(num)):
# Leading zero check
if end > index and num[index] == '0':
break
current_number = (
current_number * 10 + int(num[end])
)
# 32-bit integer overflow check
if current_number > MAX_INT:
break
# Fibonacci validation
if len(sequence) >= 2:
expected = sequence[-1] + sequence[-2]
if current_number < expected:
continue
if current_number > expected:
break
# Choose
sequence.append(current_number)
# Explore
if backtrack(end + 1):
return True
# Undo choice
sequence.pop()
return False
if backtrack(0):
return sequence
return []
The implementation uses recursive backtracking to construct the sequence incrementally.
The sequence list stores the current Fibonacci-like numbers being explored.
The recursive function backtrack(index) attempts to build a valid sequence starting from position index in the string.
Inside the recursion, we progressively construct numbers digit by digit instead of slicing substrings repeatedly. This is more efficient because we avoid repeated integer conversions.
The leading zero check is critical:
if end > index and num[index] == '0':
break
This ensures that numbers like "01" are rejected immediately.
The overflow condition prevents invalid 32-bit values from entering the sequence.
The Fibonacci validation logic performs aggressive pruning:
- If the current number is too small, we continue extending the substring.
- If it becomes too large, we stop immediately because additional digits only increase the value.
- Only exact matches proceed recursively.
Finally, backtracking removes failed choices using sequence.pop() so that other possibilities can be explored cleanly.
Go Solution
func splitIntoFibonacci(num string) []int {
const MAX_INT = 1<<31 - 1
sequence := []int{}
var backtrack func(index int) bool
backtrack = func(index int) bool {
if index == len(num) {
return len(sequence) >= 3
}
currentNumber := 0
for end := index; end < len(num); end++ {
// Leading zero check
if end > index && num[index] == '0' {
break
}
currentNumber = currentNumber*10 + int(num[end]-'0')
// Overflow check
if currentNumber > MAX_INT {
break
}
// Fibonacci validation
if len(sequence) >= 2 {
expected := sequence[len(sequence)-1] +
sequence[len(sequence)-2]
if currentNumber < expected {
continue
}
if currentNumber > expected {
break
}
}
// Choose
sequence = append(sequence, currentNumber)
// Explore
if backtrack(end + 1) {
return true
}
// Undo choice
sequence = sequence[:len(sequence)-1]
}
return false
}
if backtrack(0) {
return sequence
}
return []int{}
}
The Go implementation follows the same recursive structure as the Python version.
One important difference is integer handling. Go uses explicit integer arithmetic, so we carefully ensure values never exceed 2^31 - 1.
Slice backtracking is handled using:
sequence = sequence[:len(sequence)-1]
Unlike Python, Go does not distinguish between nil and empty slices in LeetCode outputs, so returning []int{} is perfectly acceptable.
Worked Examples
Example 1
Input: "1101111"
Possible valid answer:
[11, 0, 11, 11]
Step-by-step exploration:
| Step | Current Sequence | Remaining String | Action |
|---|---|---|---|
| 1 | [] | "1101111" | Try first number = 1 |
| 2 | [1] | "101111" | Try second number = 1 |
| 3 | [1,1] | "01111" | Expected next = 2 |
| 4 | [1,1] | "01111" | Next substring starts with 0, invalid |
| 5 | [] | "1101111" | Backtrack |
| 6 | [11] | "01111" | Try second number = 0 |
| 7 | [11,0] | "1111" | Expected next = 11 |
| 8 | [11,0,11] | "11" | Match found |
| 9 | [11,0,11] | "11" | Expected next = 11 |
| 10 | [11,0,11,11] | "" | Success |
Example 2
Input: "112358130"
Expected Fibonacci progression:
1, 1, 2, 3, 5, 8
Remaining string:
130
But:
5 + 8 = 13
After consuming "13":
Remaining = "0"
Now:
8 + 13 = 21
But the remaining digit is "0".
No valid continuation exists, so the algorithm exhausts all possibilities and returns:
[]
Example 3
Input: "0123"
The algorithm starts with:
first = 0
The next substring candidate could become "1".
However, trying "01" as a number is invalid because multi-digit numbers cannot begin with zero.
All branches fail, so the result is:
[]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n^2) in practice | Limited branching due to Fibonacci constraints |
| Space | O(n) | Recursion stack and sequence storage |
The algorithm initially explores possible first and second numbers, which produces roughly O(n^2) combinations.
After the first two numbers are fixed, the remaining sequence becomes deterministic because every next number must equal the sum of the previous two.
Additionally, pruning is extremely effective because:
- leading zeroes terminate branches early,
- overflow cuts off large values,
- mismatched sums stop exploration immediately.
The recursion depth is at most O(n) because every recursive call consumes at least one digit.
Test Cases
from typing import List
sol = Solution()
assert sol.splitIntoFibonacci("123456579") == [123, 456, 579] # standard valid case
result = sol.splitIntoFibonacci("1101111")
assert result in (
[11, 0, 11, 11],
[110, 1, 111]
) # multiple valid answers
assert sol.splitIntoFibonacci("11235813") == [1, 1, 2, 3, 5, 8, 13] # classic Fibonacci
assert sol.splitIntoFibonacci("112358130") == [] # impossible continuation
assert sol.splitIntoFibonacci("0123") == [] # invalid leading zero
assert sol.splitIntoFibonacci("0000") == [0, 0, 0, 0] # all zeroes valid
assert sol.splitIntoFibonacci("1011") == [1, 0, 1, 1] # zero inside sequence
assert sol.splitIntoFibonacci("214748364721474836422147483641") == [] # overflow case
assert sol.splitIntoFibonacci("123") == [1, 2, 3] # minimum valid length
assert sol.splitIntoFibonacci("11111111111111111111") == [] # many repeated digits
assert sol.splitIntoFibonacci("539834657215398346785") == [] # no valid decomposition
assert sol.splitIntoFibonacci("12122436") == [12, 12, 24, 36] # larger values
| Test | Why |
|---|---|
"123456579" |
Standard successful decomposition |
"1101111" |
Multiple valid outputs |
"11235813" |
Canonical Fibonacci sequence |
"112358130" |
Valid prefix but impossible completion |
"0123" |
Leading zero rejection |
"0000" |
Zero handling |
"1011" |
Internal zero values |
| Overflow example | Verifies 32-bit constraint |
"123" |
Smallest valid sequence |
| Repeated ones | Stress test for pruning |
| Large invalid input | Deep backtracking scenario |
"12122436" |
Multi-digit Fibonacci values |
Edge Cases
Leading Zeroes
Inputs like "0123" are tricky because "01" looks numerically valid after conversion, but violates the problem rules.
A naive implementation might accidentally parse "01" as integer 1 and incorrectly accept the sequence.
The implementation prevents this using:
if end > index and num[index] == '0':
break
This guarantees that once a number begins with '0', it can only contain that single digit.
Integer Overflow
The problem explicitly restricts values to signed 32-bit integers.
Without overflow checks, very long substrings could produce integers larger than allowed, causing incorrect results or language-specific overflow behavior.
The implementation continuously checks:
if current_number > 2**31 - 1:
break
Since appending digits only increases the number, the branch can be safely abandoned immediately.
Multiple Valid Answers
Some inputs can produce more than one valid Fibonacci decomposition.
For example:
"1101111"
can generate:
[11,0,11,11]
or:
[110,1,111]
The problem allows returning any valid sequence.
The backtracking implementation naturally returns the first valid sequence it discovers, which satisfies the requirement.