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 from i 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 our ans (answer) list and then recursively call the function to build on the sequence from the next position j + 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 index i. The base case for the recursion is when i 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 returns True.
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 from ans, 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 index i to the end of the string n. This is done by multiplying x 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 number 0 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 add x. If ans already has two or more numbers, then x is only added if it's the sum of the last two numbers in ans.
- If x doesn't satisfy the Fibonacci-like condition, the inner loop breaks to try a different starting point for the next number.
Further Recursion: When a valid number x is found and appended to ans, the dfs function is called recursively with the next starting index j + 1. If the recursive call returns True, indicating that a complete and valid sequence has been found, the current function also returns True.
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 number x.
Returning the Result: The solution defines the list ans to store the numbers of the Fibonacci-like sequence. If the dfs function eventually returns True, 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 Evaluator

Example 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 with i = 0.
The first loop tries to form a number x by considering each substring starting from the index i. 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 add x = 1 to ans and call dfs recursively with i = 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 to ans.
Now ans = [1, 1]. With a new recursive call, we move to i = 2 and try to form the next number.
x now is 2 which is the sum of the last two numbers in ans. We add x = 2 to ans, making ans = [1, 1, 2] and call dfs recursively with i = 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, and x = 8 respectively, with each satisfying the Fibonacci-like property and getting added to ans.
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, then x = 2, but the next number formed would be 3, which does not equal 1 + 2.
The process would backtrack, trying different combinations (next x would be 23), 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 string num, let's denote the length as n. Hence, a simple upper-bound on the recursion depth is O(n).
Inside each call of dfs, there is a loop that generates the next potential number in the sequence, which can run up to n times. In the worst case, this loop will iterate n 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 in O(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 of O(n).
The space to store the ans list, in the worst case, is also O(n), as the maximum possible length of the list is n when every digit in num 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don’t know