Split Array into Fibonacci Sequence: Backtracking with Pruning

Given a string of digits num, split it into a Fibonacci-like sequence. Each number in the sequence (after the first two) must equal the sum of the two preceding numbers. Every number must fit in a 32-bit signed integer (at most 2^31 - 1). Return any valid split, or an empty list if none exists.

This is LeetCode 842: Split Array into Fibonacci Sequence. It combines string partitioning with the Fibonacci property, and the key challenge is navigating the search space efficiently. If you have solved Restore IP Addresses or Palindrome Partitioning, you already know the core idea: use backtracking to try every possible way to split a string, pruning invalid branches early.

Why this problem matters

Split Array into Fibonacci Sequence is a great drill for constrained backtracking on strings. Unlike pure enumeration problems where you collect all valid answers, this problem asks you to find just one valid split and return immediately. That means your backtracking needs an early exit: the moment you find a valid sequence, stop searching.

It also forces you to handle two tricky constraints that come up in many string-splitting problems:

1. Leading zeros. A number like "01" is not valid (unless the number itself is just "0"). You need to detect this and prune the branch.
2. Integer overflow. Each number must be at most 2^31 - 1. If parsing a substring produces a value that exceeds this limit, you can stop extending that substring because adding more digits only makes it larger.

These two constraints are the pruning mechanisms that keep the exponential search space manageable.

The key insight

The first two numbers in the sequence completely determine the rest. Once you fix the first number and the second number, every subsequent number is forced: it must equal the sum of the two before it. So the algorithm only needs to search over choices for the first two numbers. After that, it greedily checks whether the remaining string matches the required sequence.

This means the backtracking is really a two-phase process:

1. Choose phase: Try all possible lengths for the first and second numbers.
2. Verify phase: Once two numbers are fixed, check if the rest of the string forms the required Fibonacci continuation.

The "verify" phase is still done inside the same recursive function. When result has fewer than two elements, we try all possible next numbers. When it has two or more, we only try the one number that equals result[-1] + result[-2]. That constraint dramatically reduces the branching factor from exponential to linear after the first two choices.

The backtracking solution

def splitIntoFibonacci(num: str) -> list[int]:
    result = []

    def backtrack(index: int) -> bool:
        if index == len(num) and len(result) >= 3:
            return True

        for length in range(1, len(num) - index + 1):
            if num[index] == '0' and length > 1:
                break

            value = int(num[index:index + length])
            if value > 2**31 - 1:
                break

            if len(result) >= 2 and value > result[-1] + result[-2]:
                break

            if len(result) < 2 or value == result[-1] + result[-2]:
                result.append(value)
                if backtrack(index + length):
                    return True
                result.pop()

        return False

    backtrack(0)
    return result

Let's walk through the logic.

The outer function initializes an empty result list and calls backtrack(0). The recursive function tries to parse numbers starting at index in the string.

Base case: if index equals the length of the string and we have at least 3 numbers, we found a valid Fibonacci split. Return True to stop the search.

Loop: we try every possible length for the next number, starting from 1 digit up to however many digits remain.

Leading-zero pruning: if the character at index is '0' and we are trying a length greater than 1, we break. A number like "01" or "007" is not valid. Note that a single "0" is fine, so we only break when length > 1. We use break instead of continue because all longer lengths will also have the same leading zero.

Overflow pruning: if the parsed value exceeds 2^31 - 1, we break. Longer substrings will only produce larger values.

Fibonacci pruning: if we already have two or more numbers and the current value exceeds the required sum, we break. Again, longer substrings produce larger values, so no point continuing.

Choose-explore-unchoose: if we have fewer than two numbers (still choosing the first two), or the value matches the required sum, we append it, recurse, and pop it on backtrack. If the recursive call returns True, we propagate the success upward immediately.

Visual walkthrough

Let's trace through the algorithm with num = "1101111". Watch how different splits are tried and pruned.

Notice how the algorithm tries single-character splits first. The leading-zero check catches "01" immediately. The longer path [1, 1, 0, 1, 1] fails because the remaining digits cannot form the required next number. Only when the algorithm tries "11" as the first number does it find the valid split [11, 0, 11, 11].

Complexity analysis

Time: in the worst case, we try every possible partition of the string. There are 2^(n-1) ways to place dividers between n characters. For each partition, we do O(n) work to parse and compare numbers. In practice, the pruning (leading zeros, overflow, Fibonacci constraint) eliminates most branches, and the algorithm runs much faster than the worst case.

Space: the recursion stack goes at most n levels deep (one level per character in the worst case). The result list also holds at most n numbers. So the auxiliary space is O(n).

Edge cases

Before submitting, make sure you handle these:

• Leading zeros: "0000" should return [0, 0, 0, 0] (single zeros are valid). But "01" as a multi-digit number is not allowed.
• Integer overflow: each number must be at most 2^31 - 1 (2147483647). A string like "21474836472147483647" needs careful handling. Always check before appending.
• Too few numbers: the result must have at least 3 numbers. A string like "11" cannot be split into a valid Fibonacci sequence because you need at least three elements.
• No valid split: return an empty list, not None or an error.
• Large sums: even if individual numbers fit in 32 bits, their sum might not. In Python this is not an issue (arbitrary precision), but the problem constrains each number in the result to 32-bit range.

The building blocks

This problem is built on two core reusable pieces that CodeBricks drills independently.

Backtracking template (choose-explore-unchoose)

The same skeleton from Combination Sum, Palindrome Partitioning, and Restore IP Addresses:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)
        backtrack(next_state)
        undo_choice(choice)

In this problem, make_choice is result.append(value). backtrack recurses with the new index. undo_choice is result.pop(). The key variation is the early return True that stops the search after finding the first valid split.

Pruning with constraints

Three pruning rules keep the search space small:

1. Leading zeros: if the digit at the current index is '0', only allow a single-character number.
2. Overflow: if the parsed value exceeds 2^31 - 1, stop trying longer substrings.
3. Fibonacci constraint: if the value already exceeds the required sum, stop. Longer substrings will only be larger.

Each rule uses break instead of continue because all subsequent iterations (with longer substrings) will also violate the same constraint. This is a pattern you will see in many string-splitting problems.

Common mistakes

1. Using continue instead of break for leading zeros. If num[index] is '0', any multi-digit number starting here has a leading zero. Since you are iterating over increasing lengths, break is correct. Using continue skips the current length but still checks longer ones, which are all equally invalid.

2. Forgetting the overflow check. Without checking value > 2^31 - 1, you might add numbers that exceed 32-bit range. The problem explicitly requires each number to fit in a 32-bit signed integer.

3. Requiring exactly 3 numbers instead of at least 3. The problem says the sequence must have at least 3 elements. A valid result can have 4, 5, or more numbers. The base case should check len(result) >= 3, not len(result) == 3.

4. Not returning early on success. This problem asks for any valid split, not all valid splits. If your backtracking does not propagate True upward, it will continue searching after finding a valid answer, wasting time and potentially overwriting the result.

From understanding to recall

You understand the backtracking structure. You see how leading-zero pruning, overflow checks, and the Fibonacci constraint keep the search space small. But can you write this solution from scratch in under three minutes without looking at the code?

That is what interviews test. The tricky parts are the three break conditions and remembering to check len(result) >= 3 (not == 3) in the base case. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the backtracking loop with its three pruning rules from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "split string into Fibonacci" and the code flows out without hesitation.

The backtracking-with-pruning template is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Combination Sum - Another backtracking problem using the choose-explore-unchoose template. Shows how the same skeleton adapts for different constraints (reuse allowed, sum target).
• Palindrome Partitioning - Splitting a string into valid parts using backtracking. Very similar structure to Fibonacci splitting, but the validity check is "is palindrome" instead of "matches Fibonacci sum."
• Restore IP Addresses - Another string-splitting backtracking problem with numeric constraints. Same leading-zero handling and similar pruning approach.

CodeBricks breaks Split Array into Fibonacci Sequence into its backtracking building block, then drills it independently with spaced repetition. You type the backtracking skeleton with its three pruning rules from scratch until it is automatic. When a string-splitting backtracking problem shows up in your interview, you do not think about it. You just write it.