842. Split Array into Fibonacci Sequence
Problem Description
In this problem, we are provided with a string num
which represents a sequence of digits. Our goal is to check if we can split this string into a sequence of non-negative integers such that the sequence forms a Fibonacci-like series. A Fibonacci-like series is one where every number in the series is the sum of the two preceding numbers, just like in the Fibonacci series but it does not necessarily start with 0 and 1.
There are a few constraints we need to consider:
- Each number in the series must be less than
2**31
and fit within a 32-bit signed integer. - The length of the series must be at least 3.
- There should be no leading zeroes in any number of the series, except if the number itself is zero.
If we can form such a sequence, we should return the sequence. If it's not possible, we should return an empty list.
Flowchart Walkthrough
Let's analyze LeetCode Problem 842, where the task is to Split Array into Fibonacci Sequence using the Flowchart. Here's a detailed explanation on how we can arrive at using the Backtracking pattern:
-
Is it a graph?
- No: The problem does not involve nodes and edges typical to graphical problems.
-
Need to solve for kth smallest/largest?
- No: The task is about splitting an array to form a Fibonacci sequence, not finding a specific smallest or largest value.
-
Involves Linked Lists?
- No: This problem deals with strings or arrays, not linked lists.
-
Does the problem have small constraints?
- Yes: While the overall input might not be extremely small, the task’s nature of trying to partition a string into numbers that form a Fibonacci sequence suggests an exhaustive search within reasonable limits, as each number affects subsequent choices.
-
Brute force / Backtracking?
- Yes: Given that we need to explore multiple ways of splitting the numbers and ensure they form a valid Fibonacci sequence, using brute force or backtracking is suitable to recursively try different partitionings and backtrack when a sequence cannot be extended into a Fibonacci triplet.
Conclusion: Based on the flowchart, using the backtracking approach is suitable for recursively generating possible partitions of the array into successive Fibonacci numbers and backtracking if a sequence does not meet the necessary criteria.
Intuition
Our solution strategy involves trying to build the Fibonacci-like sequence from the start of the string by making choices at each step and using backtracking to explore other possibilities if a certain choice doesn't lead to a solution.
Here's the intuition behind the steps we take in our approach:
- We need to keep track of the current position in the string we're trying to convert into the next number in the sequence. This is managed by the index
i
. - For the current position
i
, we try to extract each possible number (which doesn't have leading zeroes) by iterating through the string fromi
to the end. Leading zeroes are invalid (except for the number 0 itself), so if we encounter a zero as the first character of a number (and it's not a standalone zero), we stop trying to build further from this position. - For each number
x
we consider, we check if it's valid by making sure it doesn't exceed the 32-bit integer limit and that it fits the Fibonacci-like requirement (if we already have at least two numbers in our current sequence). - If
x
fits as the next number in the series, we add it to ourans
(answer) list and then recursively call the function to build on the sequence from the next positionj + 1
. - We're essentially performing a depth-first search (DFS) to exhaust all possibilities, and whenever our recursion finishes processing the string and we have more than two numbers in our sequence (
ans
), we've found a valid Fibonacci-like sequence. - If at any point, a choice of
x
does not lead to a valid sequence, we backtrack by removing the last added number and trying the next possibility.
This is a backtracking problem where we build partial solutions and backtrack as soon as we realize the current path does not lead to a valid full solution. The combination of iterative exploration of each number that could be added from a certain position with the recursive call to continue the sequence from the next character is essential. The use of backtracking helps in reducing the time complexity since we prune the search tree by stopping the exploration of sequences that can no longer be valid as early as possible.
Learn more about Backtracking patterns.
Solution Approach
The reference solution uses Depth First Search (DFS) and backtracking to find a Fibonacci-like sequence from the given string. The implementation of this approach is written in Python and uses recursion to iterate over the possibilities when constructing the sequence. Here is a rundown of the approach, with reference to the solution code provided:
-
Depth First Search (DFS) and Recursion: The
dfs
function is a recursive method that is called with the current indexi
. The base case for the recursion is wheni
equals the length of the given string,n
. If we reach the base case and the current answer list,ans
, contains more than two numbers, it means a valid sequence has been formed, and the function returnsTrue
. -
Backtracking: The
ans
list serves as a partial solution that is constructed incrementally. If at any step the sequence can no longer be continued (either because the next number is too big or does not fit the Fibonacci-like property), the last element is removed fromans
, and the function backtracks to try other possibilities. -
Constructing Numbers: A nested loop is used to construct the next number
x
in the sequence by adding digits one by one from the current indexi
to the end of the stringn
. This is done by multiplyingx
by 10 and adding the integer value of the current digit. Special care is taken to skip any numbers that would start with a leading zero (except the number0
itself), as per the rules of the problem. -
Checking Validity: After each number
x
is constructed, several checks are performed:- The number must be less than
2**31 - 1
, otherwise, we stop considering longer numbers. - The algorithm checks if the length of
ans
is less than 2, which means we don't have enough numbers to compare for the Fibonacci-like property and just addx
. Ifans
already has two or more numbers, thenx
is only added if it's the sum of the last two numbers inans
. - If
x
doesn't satisfy the Fibonacci-like condition, the inner loop breaks to try a different starting point for the next number.
- The number must be less than
-
Further Recursion: When a valid number
x
is found and appended toans
, thedfs
function is called recursively with the next starting indexj + 1
. If the recursive call returnsTrue
, indicating that a complete and valid sequence has been found, the current function also returnsTrue
. -
Pop and Continue: If the recursive call doesn't yield a solution, the last number is popped from
ans
(this is the backtracking step), and the search continues with the next possible numberx
. -
Returning the Result: The solution defines the list
ans
to store the numbers of the Fibonacci-like sequence. If thedfs
function eventually returnsTrue
,ans
will be returned, containing a valid sequence. If no sequence is found, the list remains empty, and an empty list is returned.
In summary, the solution leverages recursion, backtracking, and careful construction of candidate numbers while following the constraints of the problem. These elements combined enable the algorithm to explore the space of all possible sequences efficiently and effectively to arrive at the desired result or determine that no solution exists.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the solution approach to a small example to illustrate how it works. Consider the string num = "112358"
which is a classic Fibonacci-like sequence starting with 1, 1, 2, 3, 5, and 8.
- We start with an empty answer list
ans
and at the first character of the string withi = 0
. - The first loop tries to form a number
x
by considering each substring starting from the indexi
. At the start,x
is 1 (the first character). - Since
ans
is empty, we don't need to check for the Fibonacci-like property yet. We addx = 1
toans
and calldfs
recursively withi = 1
. - The recursive call starts again from
i = 1
, trying to form the next number. It takes the next character, which is 1, and since it's still valid,x = 1
is added toans
. - Now
ans = [1, 1]
. With a new recursive call, we move toi = 2
and try to form the next number. x
now is2
which is the sum of the last two numbers inans
. We addx = 2
toans
, makingans = [1, 1, 2]
and calldfs
recursively withi = 3
.- The recursive calls continue, with each call attempting to construct the next number following the Fibonacci-like property.
- We proceed to positions 4, 5, and 6 in the string forming
x = 3
,x = 5
, andx = 8
respectively, with each satisfying the Fibonacci-like property and getting added toans
. - When
i
reaches the end of the string (i.e.,i = n
), the base case is reached.ans
contains more than two numbers (ans = [1, 1, 2, 3, 5, 8]
), so we have successfully found a valid sequence. - The recursive calls start to unwind, each returning
True
since a valid sequence has been built.
At the end of this process, the result is the sequence [1, 1, 2, 3, 5, 8]
which confirms that 112358
can indeed be split into a Fibonacci-like sequence.
Conversely, if we had started with a string that could not form such a sequence, like num = "123456789"
:
- We start with
x = 1
, thenx = 2
, but the next number formed would be3
, which does not equal1 + 2
. - The process would backtrack, trying different combinations (next
x
would be23
), but since there is no combination that works, it would eventually fail. - After exhausting all possibilities, the recursive calls would not satisfy the condition and would return an empty list, indicating that no valid Fibonacci-like sequence is found.
Solution Implementation
1from typing import List
2
3class Solution:
4 def splitIntoFibonacci(self, num: str) -> List[int]:
5 # Helper function to perform depth-first search for Fibonacci sequence
6 def dfs(start_index):
7 # If the start_index reached the end of the string, and we have at least three numbers, we found a sequence
8 if start_index == string_length:
9 return len(fib_sequence) > 2
10
11 # To store the current number we're building from the string
12 current_number = 0
13 for index in range(start_index, string_length):
14 # Avoid numbers with leading 0, except for 0 itself
15 if index > start_index and num[start_index] == '0':
16 break
17
18 # Accumulate the number from the string
19 current_number = current_number * 10 + int(num[index])
20 # If the number is larger than the maximum allowed for int32 or cannot be a part of the sequence, stop
21 if current_number > 2**31 - 1 or (len(fib_sequence) > 2 and current_number > fib_sequence[-2] + fib_sequence[-1]):
22 break
23
24 # If the sequence is less than two or forms a valid Fibonacci sequence, continue
25 if len(fib_sequence) < 2 or fib_sequence[-2] + fib_sequence[-1] == current_number:
26 fib_sequence.append(current_number)
27 # Recurse and if the sequence is found, return True
28 if dfs(index + 1):
29 return True
30 # Backtrack if the sequence does not work
31 fib_sequence.pop()
32 return False
33
34 # Get the length of the input string
35 string_length = len(num)
36 # List to store the valid Fibonacci sequence
37 fib_sequence = []
38 # Start DFS from index 0
39 dfs(0)
40 # Return the found Fibonacci sequence
41 return fib_sequence
42
1class Solution {
2 private List<Integer> fibonacciSequence = new ArrayList<>();
3 private String sequence;
4
5 // Initiates the process to split the given string into a Fibonacci sequence
6 public List<Integer> splitIntoFibonacci(String sequence) {
7 this.sequence = sequence;
8 if (depthFirstSearch(0)) {
9 return fibonacciSequence;
10 }
11 // If no valid sequence is found, return an empty list
12 return new ArrayList<>();
13 }
14
15 // Helper method to perform depth-first search to build the Fibonacci sequence
16 private boolean depthFirstSearch(int index) {
17 // Base case: If at the end of string and we have at least 3 numbers, return true
18 if (index == sequence.length()) {
19 return fibonacciSequence.size() >= 3;
20 }
21
22 long currentValue = 0; // Using long to prevent integer overflow
23 for (int endIndex = index; endIndex < sequence.length(); endIndex++) {
24 // Break if the number starts with zero and is not just "0"
25 if (endIndex > index && sequence.charAt(index) == '0') {
26 break;
27 }
28
29 // Construct the current number
30 currentValue = currentValue * 10 + sequence.charAt(endIndex) - '0';
31
32 // Break if current value is greater than Integer.MAX_VALUE
33 if (currentValue > Integer.MAX_VALUE) {
34 break;
35 }
36
37 int size = fibonacciSequence.size();
38
39 // Break if the current value is greater than the sum of the last two numbers in the sequence
40 if (size >= 2 && currentValue > fibonacciSequence.get(size - 1) + fibonacciSequence.get(size - 2)) {
41 break;
42 }
43
44 // If the sequence is fewer than 2 numbers or currentValue is the sum of the last two, try to extend the sequence
45 if (size < 2 || currentValue == fibonacciSequence.get(size - 1) + fibonacciSequence.get(size - 2)) {
46 // Add the current value to the sequence
47 fibonacciSequence.add((int) currentValue);
48
49 // Recur, and if a valid sequence is found deeper, return true
50 if (depthFirstSearch(endIndex + 1)) {
51 return true;
52 }
53
54 // If no valid extension is found, backtrack by removing the last number
55 fibonacciSequence.remove(fibonacciSequence.size() - 1);
56 }
57 }
58
59 // If no sequence is found return false
60 return false;
61 }
62}
63
1class Solution {
2public:
3 // This function splits a string into a Fibonacci sequence
4 // and returns it as a vector of integers.
5 vector<int> splitIntoFibonacci(string num) {
6 int n = num.size();
7 vector<int> sequence; // This vector will store the resulting Fibonacci sequence.
8
9 // This lambda function tries to find a Fibonacci sequence starting from index i
10 // using Depth First Search.
11 function<bool(int)> dfs = [&](int startIndex) -> bool {
12 if (startIndex == n) {
13 // If we reach the end of the string and have at least 3 numbers, we found a sequence.
14 return sequence.size() > 2;
15 }
16
17 long long currentValue = 0; // To avoid integer overflow issues.
18
19 // Iterate over the string starting from index 'startIndex' to form a number.
20 for (int endIndex = startIndex; endIndex < n; ++endIndex) {
21 // Prevent leading zeroes in a number unless the number is zero itself.
22 if (endIndex > startIndex && num[startIndex] == '0') {
23 break;
24 }
25
26 // Build the number by appending the next digit.
27 currentValue = currentValue * 10 + num[endIndex] - '0';
28
29 // Break the loop if the number exceeds integer limit or
30 // if it is larger than the sum of last two numbers of current sequence.
31 if (currentValue > INT_MAX || (sequence.size() > 1 && currentValue > (long long) sequence[sequence.size() - 1] + sequence[sequence.size() - 2])) {
32 break;
33 }
34
35 // If the sequence is less than two numbers long or the current number completes a Fibonacci sequence,
36 // push it onto the stack and continue the search recursively.
37 if (sequence.size() < 2 || currentValue == (long long) sequence[sequence.size() - 1] + sequence[sequence.size() - 2]) {
38 sequence.push_back(currentValue);
39 // Recursively call dfs with the next starting index and check if the sequence can be completed.
40 if (dfs(endIndex + 1)) {
41 return true;
42 }
43 // Backtrack if adding current number doesn't lead to a solution.
44 sequence.pop_back();
45 }
46 }
47
48 return false; // Return false if no sequence is found starting from index 'startIndex'.
49 };
50
51 // Start the Depth First Search from the first index.
52 dfs(0);
53
54 // Return the Fibonacci sequence found, this will be empty if no sequence was found.
55 return sequence;
56 }
57};
58
1// TypeScript version of the Fibonacci sequence finder.
2
3// This array stores the resulting Fibonacci sequence.
4let sequence: number[] = [];
5
6// The main function that initiates the Fibonacci sequence split.
7function splitIntoFibonacci(num: string): number[] {
8 const n: number = num.length;
9 sequence = []; // Clearing the previous sequence
10
11 // Helper function that utilizes Depth First Search to build the Fibonacci sequence.
12 const dfs = (startIndex: number): boolean => {
13 if (startIndex === n) {
14 // If we reach the end of the string and have at least 3 numbers, we found a sequence.
15 return sequence.length > 2;
16 }
17
18 let currentValue: number = 0; // To handle potentially large numbers safely.
19
20 // Iterate over the string to form a number starting from index 'startIndex'.
21 for (let endIndex = startIndex; endIndex < n; endIndex++) {
22 // Prevent leading zeroes in a number unless the number is zero itself.
23 if (endIndex > startIndex && num[startIndex] === '0') {
24 break;
25 }
26
27 // Adding the next digit to build the number.
28 currentValue = currentValue * 10 + parseInt(num[endIndex], 10);
29
30 // If the number is too large or does not fit the Fibonacci property, exit loop.
31 if (
32 currentValue > Number.MAX_SAFE_INTEGER ||
33 (sequence.length > 1 && currentValue > sequence[sequence.length - 1] + sequence[sequence.length - 2])
34 ) {
35 break;
36 }
37
38 // Check if we can push the current value to the sequence.
39 if (sequence.length < 2 || currentValue === sequence[sequence.length - 1] + sequence[sequence.length - 2]) {
40 sequence.push(currentValue);
41
42 // Continue building the sequence with a recursive call.
43 if (dfs(endIndex + 1)) {
44 // If the recursive call returns true, the sequence is completed.
45 return true;
46 }
47
48 // If the current path does not lead to a solution, backtrack.
49 sequence.pop();
50 }
51 }
52
53 // If no sequence is found starting from 'startIndex', return false.
54 return false;
55 };
56
57 // Start the search for the Fibonacci sequence from the first index.
58 dfs(0);
59
60 // Return the sequence found (empty array if no valid sequence was found).
61 return sequence;
62}
63
64// Sample usage:
65const numString: string = "112358130"; // Input number as a string
66const fibSequence: number[] = splitIntoFibonacci(numString);
67console.log(fibSequence); // Output the Fibonacci sequence found.
68
Time and Space Complexity
The provided code snippet is a Python method splitIntoFibonacci
which attempts to split a given numeric string into a Fibonacci-like sequence where each number is the sum of the preceding two. Here's the analysis of the time and space complexity:
Time Complexity
The primary driver of the time complexity is the depth-first search (dfs
) function which explores all possible combinations to construct a Fibonacci-like sequence:
-
The
dfs
function is recursive and in the worst case, the depth of the recursion is the length of the stringnum
, let's denote the length asn
. Hence, a simple upper-bound on the recursion depth isO(n)
. -
Inside each call of
dfs
, there is a loop that generates the next potential number in the sequence, which can run up ton
times. In the worst case, this loop will iteraten
times for each level of recursion. -
Checking whether a number can be added to the sequence (
if len(ans) < 2 or ans[-2] + ans[-1] == x:
) is done inO(1)
time.
Combining these aspects, the worst-case time complexity of the algorithm is O(n^2 * n)
= O(n^3)
because you may generate up to n
numbers for each of the n
recursive calls, and for each number, you might iterate through up to n
digits to construct it.
Space Complexity
The space complexity depends on the storage required for the recursive call stack and the list ans
:
-
The recursive call stack can go up to
n
deep in the worst case, which gives a space usage ofO(n)
. -
The space to store the
ans
list, in the worst case, is alsoO(n)
, as the maximum possible length of the list isn
when every digit innum
is a single-digit number in the Fibonacci sequence.
Thus, the overall space complexity of the algorithm is O(n)
due to the recursive call stack and the storage for the sequence ans
.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.