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, andf[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 <= 200num contains only digits.Problem Overview: You receive a numeric string and must split it into a sequence of integers that forms a valid Fibonacci sequence. Each number must equal the sum of the previous two, contain no leading zeros (unless the number is 0), and fit within a 32‑bit signed integer.
Approach 1: Backtracking and Recursion (Time: O(n^3), Space: O(n))
This approach tries every possible split for the first two numbers, then recursively checks whether the rest of the string can extend the Fibonacci sequence. Start by choosing indices i and j to define the first two numbers. From there, compute the expected next value as a + b and check whether the string starting at the current index begins with that value. If it matches, append it to the sequence and continue recursively. The backtracking stops early when a number exceeds the 32‑bit integer limit or when the substring does not match the required Fibonacci sum. Time complexity is roughly O(n^3) in the worst case due to trying splits and substring comparisons, while space complexity is O(n) for the recursion stack and sequence storage. This approach directly models the sequence-building process and is commonly implemented using backtracking over a string.
Approach 2: Iterative Parsing with Dynamic Updates (Time: O(n^2), Space: O(n))
This method removes recursion and builds the sequence iteratively. Loop over possible lengths for the first and second numbers, parse them, and then repeatedly compute the next expected Fibonacci value. Convert the sum to a string and check whether the remaining substring begins with that value. If it matches, advance the pointer and continue generating numbers until the string is consumed. The key optimization is avoiding repeated branching: once the first two numbers are fixed, the rest of the sequence is deterministic. Time complexity becomes about O(n^2) because you only try combinations of the first two numbers and then extend linearly. Space complexity remains O(n) to store the resulting sequence. This iterative approach works well in languages like Java or C# where explicit control over parsing and bounds checking is convenient.
Recommended for interviews: The backtracking approach demonstrates understanding of search space pruning and constraint handling. However, interviewers often prefer the iterative extension method because once the first two numbers are chosen the rest of the sequence is forced, reducing unnecessary recursion. Showing both reasoning paths—brute exploration followed by deterministic extension—demonstrates strong problem-solving depth.
This approach uses backtracking to recursively split the string into all potential combinations of integers and checks if they form a valid Fibonacci sequence.
This Python code implements a backtracking solution to split the input string into potential Fibonacci sequences.
backtrack is defined to recursively attempt to form a sequence.Python
JavaScript
Time Complexity: O(2^n), since each combination of splitting points is considered recursively.
Space Complexity: O(n), for the recursion stack and the result list.
This approach involves iteratively parsing possible substrings and dynamically checking for valid Fibonacci sequences.
This Java code uses an iterative method to find Fibonacci-like sequences.
isValid function checks if extending the sequence remains valid.Time Complexity: O(n^3), due to nested loops exploring potential splits and sequence validity.
Space Complexity: O(n), primarily to store intermediate sequence results.
| Approach | Complexity |
|---|---|
| Backtracking and Recursion | Time Complexity: O(2^n), since each combination of splitting points is considered recursively. Space Complexity: O(n), for the recursion stack and the result list. |
| Iterative Parsing with Dynamic Updates | Time Complexity: O(n^3), due to nested loops exploring potential splits and sequence validity. Space Complexity: O(n), primarily to store intermediate sequence results. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking and Recursion | O(n^3) | O(n) | When exploring all valid splits and demonstrating recursive pruning in interviews |
| Iterative Parsing with Dynamic Updates | O(n^2) | O(n) | Preferred approach once the first two numbers are fixed and the sequence becomes deterministic |
Leetcode 842 | Split Array into Fibonacci Sequence | PayPal Interview Question (Java Solution) • The Tech Granth • 4,124 views views
Watch 9 more video solutions →Practice Split Array into Fibonacci Sequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor