Domain 2MediumMEDIUM

Split Array into Fibonacci Sequence

LeetCode problem 842: Split Array into Fibonacci Sequence (medium).

Domain: medium•Updated: 2026-09-02
#String#Backtracking#Greedy

Problem Breakdown

We are given a string S consisting of digits and need to partition it into a sequence of non-negative integers FF such that:

  1. Length Constraint: The sequence must have at least 3 numbers (∣F∣≥3|F| \geq 3).
  2. Value Constraint: Each number fits within a signed 32-bit integer (0 <= F[i] <= 2^31 - 1).
  3. Recurrence Relation: F[i+2]=F[i]+F[i+1]F[i+2] = F[i] + F[i+1] for all valid indices (standard Fibonacci property).
  4. Formatting Constraint: No leading zeros allowed unless the number is exactly “0”.

Inputs & Outputs:

  • Input: String S of digits, length up to 200.
  • Output: A list of integers forming a valid sequence or an empty list if impossible.

Tricky Edge Cases:

  • Leading Zeros: Splitting “10” into [“1”, “0”] is fine (if part of seq), but splitting “05” as [“0”, “5”] is invalid because the second number has a leading zero in this context? Wait, Example 4 says S="0123" -> Output [[]]. Explanation: Leading zeroes not allowed. So if we split at index 1 (“0”), next starts with ‘1’. But wait, [“0”, “1”] is valid for the numbers themselves (single digit zero). However, splitting “0” and then “1”? The issue in Example 4 is likely that S="0123" implies if we take first num as “0”, second must be from remaining. If we split at index 1 (“0”), next starts with ‘1’. But wait, the example output says [[]]. Why? Because after taking “0” and “1”, sum is 1. Next char in S is ‘2’, expected ‘1’. Mismatch.
    • Actually, Example 4 explanation: S="0123" -> Output [] because leading zeroes are not allowed for multi-digit numbers? No, it says "01", “2”, “3” is invalid. This refers to the number formed by a substring starting with ‘0’ having length > 1.
    • So if we parse a substring like “05”, that’s invalid immediately. If we parse “0”, valid (value 0).

Intuition

A brute-force approach would try every possible partition of S into kk numbers and check the Fibonacci property, which is exponential in terms of number count (O(2N)O(2^N) or worse) because there are many ways to split a string. However, we can optimize this observation:

  1. Deterministic Future: Once the first two numbers (a, b) are chosen from the start of S, every subsequent number is mathematically determined (c=a+bc = a + b). We do not need backtracking for F[2],F[3]…F[2], F[3] \dots.
  2. Search Space Reduction: The only degrees of freedom we have to explore are the lengths (split points) of the first two numbers, a and b. Since each number must fit in a signed 32-bit integer (≈10\approx 10 digits), the loop for split points doesn’t need to go all the way to NN, but practically we can iterate valid substring lengths.
  3. Validation: For every pair of initial numbers, we simulate generating the rest of the sequence against S. If a mismatch occurs or an integer limit is exceeded at any step, that specific split point for (a, b) fails immediately.

Approach

  1. Initial Checks: Return empty list if string length <3< 3.
  2. Iterate First Number (a): Loop through possible end indices i. Extract substring S[0:i]. Check validity (no leading zeros unless “0”). Parse to integer, check against MAX_INT (231−12^{31}-1). If valid, store as num_a.
  3. Iterate Second Number (b): Loop through possible end indices j > i. Extract substring S[i:j]. Check validity (no leading zeros unless “0”). Parse to integer, check against MAX_INT. If valid, store as num_b.
  4. Simulation: With fixed a and b, iterate forward:
    • Calculate expected next value = a + b.
    • Check if the remaining string starts with this number’s digits.
    • Update pointers (i moves past current match).
    • Shift window so new numbers become previous two for sum calculation.
  5. Success Condition: If simulation consumes exactly all characters in S, return the sequence list.
  6. Failure Handling: If loop finishes without success, try next split points.

Complexity Analysis

  • Time Complexity: O(N⋅L)O(N \cdot L) where NN is string length and LL is max digits per number (bounded by integer limit ≈10\approx 10). Effectively roughly constant iterations for the outer loops (≤9\leq 9 or 1010 valid lengths) multiplied by a linear scan of S during simulation. Given constraints, this behaves close to O(N)O(N) in practice because we prune invalid splits early (overflow/leading zero checks).
  • Space Complexity: O(1)O(1) auxiliary space excluding the output list storage (O(K)O(K) where KK is sequence length), as we only store pointers and current numbers.

Solution

class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        n = len(S)
        if n < 3:
            return []
        
        MAX_INT = (1 << 31) - 1
        
        # Iterate over the length of the first number 'a'
        for i in range(1, min(n // 2 + 1, n)): 
            # Optimization: If substring is too long to fit int or has leading zero issues
            
            a_str = S[:i]
            
            # Check leading zeros constraint (only "0" allowed if len > 1)
            if i > 1 and a_str[0] == '0':
                continue
                
            try:
                num_a = int(a_str)
            except ValueError:
                continue
            
            # If number exceeds signed 32-bit integer limit, this split is invalid. 
            # Note: Python handles large ints automatically, so we must check value manually.
            if num_a > MAX_INT:
                break 
            
            # Iterate over the length of the second number 'b' starting after first number ends
            for j in range(i + 1, min(n - i // 2 + 1, n)): 
                b_str = S[i:j]
                
                if len(b_str) > 9: # Optimization check based on max int digits roughly
                    break
                
                # Check leading zeros constraint
                if (j - i) > 1 and b_str[0] == '0':
                    continue
                    
                try:
                    num_b = int(b_str)
                except ValueError:
                    continue

                if num_b > MAX_INT:
                    break
            
            # Simulation phase with fixed a and b
            curr_a, curr_b = num_a, num_b
            idx = j  # Current pointer in S after second number ends
            result = [curr_a, curr_b]
            
            while True:
                expected_sum = curr_a + curr_b
                
                if idx >= n or len(S) - idx < len(str(expected_sum)):
                    break
                
                next_str = S[idx : idx + len(str(expected_sum))]
                
                # Check for leading zero in the generated substring (if it's not just "0")
                # Actually, we must ensure that the slice matches exactly. 
                # If expected_sum is 0 and string starts with '0', valid? Yes if single digit.
                # But wait, S[idx] could be part of a larger number in input logic? No, next_str MUST match str(expected_sum)
                
                if idx + len(str(expected_sum)) > n:
                    break
                
                current_sub = S[idx : idx + len(str(expected_sum))]
                
                # Check leading zero on the substring we just matched from string (if it's not single 0)
                # Actually, since expected_sum is derived mathematically, if str(expected_sum) has no leading zeros 
                # and matches current_sub, then current_sub also won't have them. 
                # However, we must ensure that the substring in S doesn't imply a different split?
                # No, because Fibonacci property forces exact match of value. If S[idx] starts with '0' but expected_sum != 0, mismatch.
                
                if len(current_sub) > 1 and current_sub[0] == '0':
                    break
                
                if next_str != str(expected_sum):
                    # Mismatch in digits or length? 
                    # We check exact match of substring to string representation
                    pass 

                # Correct logic: Check if S[idx : idx + len(str(sum))] equals str(sum)
                
                sub_len = len(str(expected_sum))
                if idx + sub_len > n: break
                
                actual_sub = S[idx : idx + sub_len]
                
                if actual_sub != str(expected_sum):
                    # Mismatch, this pair (a,b) is invalid for the rest of string
                    curr_a, curr_b = num_a, num_b 
                    result = [curr_a, curr_b]
                    break
                
                # Update pointers and values
                idx += sub_len
                curr_a, curr_b = curr_b, expected_sum
                if len(result) == 0: pass # Just appending logic below
            
            else:
                 continue # Continue outer loop on next split attempt? No. 
                 
        return result

```python
class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        n = len(S)
        if n < 3:
            return []
        
        MAX_INT = (1 << 31) - 1
        
        # Iterate over the length of the first number 'a'
        for i in range(1, min(n // 2 + 1, n)): 
            a_str = S[:i]
            
            if len(a_str) > 9: break
            
            if len(a_str) > 1 and a_str[0] == '0': continue
            
            num_a = int(a_str)
            if num_a > MAX_INT: break 
            
            # Iterate over the length of the second number 'b' starting after first number ends
            for j in range(i + 1, min(n - i // 2 + 1, n)): 
                b_len = len(S[i:j])
                
                if b_len > 9: break
                
                if (j - i) > 1 and S[i] == '0': continue
                    
                num_b = int(S[i:j])
                if num_b > MAX_INT: break
            
            # Simulation phase with fixed a and b
            curr_a, curr_b = num_a, num_b
            idx = j 
            result = [curr_a, curr_b]
            
            while True:
                expected_sum = curr_a + curr_b
                
                if idx >= n or len(S) - idx < len(str(expected_sum)):
                    break
                
                sub_len = len(str(expected_sum))
                
                # Check leading zero constraint on the matched substring from S (if not single 0)
                actual_sub = S[idx : idx + sub_len]
                
                if len(actual_sub) > 1 and actual_sub[0] == '0': break
                
                if actual_sub != str(expected_sum):
                    curr_a, curr_b = num_a, num_b 
                    result = [curr_a, curr_b] # Reset for next iteration? No. Break simulation loop to try next split pair.
                    break
                
                idx += sub_len
                curr_a, curr_b = curr_b, expected_sum
            
            if idx == n: return result
        
        return []

```python
class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        n = len(S)
        if n < 3: