Split Array into Fibonacci Sequence

Med

#0796Time: 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).

Patterns

Backtracking

Data structures

String

Prompt

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] < 2³¹, (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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

Complexity

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

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public List<Integer> splitIntoFibonacci(String num) {3        List<Integer> result = new ArrayList<>();4        backtrack(num, 0, result);5        return result;6    }7 8    private boolean backtrack(String num, int index, List<Integer> result) {9        if (index == num.length()) {10            return result.size() >= 3;11        }12 13        long currentNum = 0;14        for (int i = index; i < num.length(); i++) {15            // Rule: no extra leading zeroes, except for the number 0 itself.16            if (num.charAt(index) == '0' && i > index) {17                break;18            }19 20            currentNum = currentNum * 10 + (num.charAt(i) - '0');21            22            // Rule: each integer fits in a 32-bit signed integer type.23            if (currentNum > Integer.MAX_VALUE) {24                break;25            }26 27            int size = result.size();28            // If we are picking the first two numbers, or if the current number29            // matches the sum of the previous two.30            if (size < 2 || currentNum == (long)result.get(size - 1) + result.get(size - 2)) {31                result.add((int) currentNum);32                // Recurse to check the rest of the string.33                if (backtrack(num, i + 1, result)) {34                    return true;35                }36                // Backtrack if the recursive call did not find a solution.37                result.remove(result.size() - 1);38            }39            // Pruning: if the current number is already larger than the expected sum,40            // any longer number from this index will also be too large.41            else if (size >= 2 && currentNum > (long)result.get(size - 1) + result.get(size - 2)) {42                break;43            }44        }45        return false;46    }47}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem