Split Array into Fibonacci Sequence - Practice Coding Problems

Split Array into Fibonacci Sequence - Problem

String Backtracking Medium

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³¹ (each integer fits in a 32-bit signed integer type)
f.length >= 3
f[i] + f[i + 1] == f[i + 2] for all 0 <= i < f.length - 2

Note: 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 an empty array if it cannot be done.

Input & Output

Example 1 — Valid Fibonacci Sequence

$ Input: num = "123456579"

› Output: [123,456,579]

💡 Note: We can split the string as "123" + "456" + "579". Since 123 + 456 = 579, this forms a valid Fibonacci-like sequence.

Example 2 — Simple Three Numbers

$ Input: num = "11235813"

› Output: [1,1,2,3,5,8,13]

💡 Note: Split as 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13. Classic Fibonacci sequence.

Example 3 — No Valid Split

$ Input: num = "199100199"

› Output: []

💡 Note: No way to split this string into a valid Fibonacci-like sequence of 3 or more numbers.

Constraints

1 ≤ num.length ≤ 200
num contains only digits

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string of digits: "123456579"

Try Splits

Attempt different ways to split into numbers

Validate Fibonacci

Check if f[i] + f[i+1] = f[i+2] for all valid i

Result

Return valid sequence or empty array

Key Takeaway

🎯 Key Insight: Once the first two numbers are chosen, the entire Fibonacci sequence is uniquely determined

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that once we fix the first two numbers in the sequence, the entire Fibonacci sequence is determined. We use backtracking to systematically try all possible splits for the first two numbers, then recursively validate if the remaining string can form a valid Fibonacci sequence. Best approach uses optimized backtracking with intelligent pruning. Time: O(2^n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Backtracking	O(n³)	O(n)	Try all possible ways to split the first two numbers and recursively check if Fibonacci pattern continues
Optimized Backtracking with Pruning	O(2^n)	O(n)	Enhanced backtracking with early termination when numbers exceed 32-bit limit or lead to impossible sequences

Brute Force with Backtracking — Algorithm Steps

Try all possible lengths for first number
For each first number, try all possible lengths for second number
Recursively check if remaining string can form Fibonacci sequence
Return first valid sequence found or empty array

Visualization

Tap to expand

Step-by-Step Walkthrough

First Split

Try different lengths for first number

Second Split

For each first number, try second number lengths

Validate

Check if remaining string follows Fibonacci pattern

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool backtrack(char* num, int index, long long* sequence, int* seqLen, int maxLen) {
    if (index == strlen(num)) {
        return *seqLen >= 3;
    }
    
    for (int i = index; i < strlen(num); i++) {
        int len = i - index + 1;
        char substr[20];
        strncpy(substr, num + index, len);
        substr[len] = '\0';
        
        if (len > 1 && substr[0] == '0') {
            break;
        }
        
        long long val = atoll(substr);
        if (val >= (1LL << 31)) {
            break;
        }
        
        if (*seqLen < 2) {
            sequence[*seqLen] = val;
            (*seqLen)++;
            if (backtrack(num, i + 1, sequence, seqLen, maxLen)) {
                return true;
            }
            (*seqLen)--;
        } else {
            if (val == sequence[*seqLen - 1] + sequence[*seqLen - 2]) {
                sequence[*seqLen] = val;
                (*seqLen)++;
                if (backtrack(num, i + 1, sequence, seqLen, maxLen)) {
                    return true;
                }
                (*seqLen)--;
            }
        }
    }
    return false;
}

int main() {
    char num[100];
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    
    long long sequence[50];
    int seqLen = 0;
    
    printf("[");
    if (backtrack(num, 0, sequence, &seqLen, 50)) {
        for (int i = 0; i < seqLen; i++) {
            if (i > 0) printf(",");
            printf("%lld", sequence[i]);
        }
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops to try all first/second number combinations, plus recursive validation

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and result array storage

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler