Additive Number: Backtracking Through Numeric Strings

Given a string of digits, you need to decide whether it can be split into a sequence where every number after the first two equals the sum of the two before it. That is 306. Additive Number, and the challenge is that you do not know where the first two numbers end. You have to try every possible split and verify whether the rest of the string follows from there.

The approach

The key insight is that once you fix the first two numbers, the entire rest of the sequence is determined. If a and b are the first two numbers, then the third must be a + b, the fourth must be b + (a+b), and so on. You have no choices left after committing to the opening split.

This turns the problem into a two-level search followed by a linear verification:

1. Try every valid split of the string into a first number a (1 to n-1 digits) and a second number b (starting right after a, at least 1 digit, ending before the string is exhausted).
2. Skip any split where a or b has a leading zero and more than one digit.
3. For the remaining splits, run check(a, b, start): compute c = a + b, verify that the string at position start begins with the digits of c, then recurse with check(b, c, start + len(str(c))).
4. If start reaches the end of the string inside check, the sequence is valid and the answer is True.

The outer loops are O(n^2) because you iterate over all pairs of cut points. Inside, check walks the rest of the string in O(n). Overall that gives O(n^3) in the worst case, but in practice most branches fail on the very first mismatch and bail out early.

Leading zeros are the main gotcha. The number 0 by itself is fine. But "01" or "007" as a multi-digit segment is not a valid number in this context, so you skip those splits before calling check.

The solution

def isAdditiveNumber(num: str) -> bool:
    n = len(num)
    def check(a, b, start):
        if start == n:
            return True
        c = a + b
        s = str(c)
        if not num.startswith(s, start):
            return False
        return check(b, c, start + len(s))
    for i in range(1, n):
        for j in range(i + 1, n):
            a_str, b_str = num[:i], num[i:j]
            if (len(a_str) > 1 and a_str[0] == '0') or (len(b_str) > 1 and b_str[0] == '0'):
                continue
            a, b = int(a_str), int(b_str)
            if check(a, b, j):
                return True
    return False

The outer two loops enumerate all candidate splits. i is where the first number ends, and j is where the second number ends. The leading-zero guard uses continue here, not break, because a different value of j with the same i might produce a valid b_str that does not start with zero.

Inside check, num.startswith(s, start) is the key operation. It checks whether the string at position start begins with the decimal representation of c. Python's str.startswith accepts an optional position argument, so this is a clean one-liner with no slicing needed. If the check passes, recurse with b and c as the new pair, advancing start by the length of c.

The recursion terminates when start == n (the whole string is consumed, return True) or when num.startswith(s, start) fails (mismatch, return False). Because Python handles arbitrarily large integers natively, this solution works correctly for very long digit strings without overflow.

Complexity analysis

Time: The two outer loops produce O(n^2) candidate splits. For each split, check walks the remaining string in O(n), doing O(n) string operations at each level of recursion. The recursion depth is bounded by the number of terms in the sequence, which is at most O(n) in the worst case (e.g., a sequence of single-digit numbers). Combined, the worst case is O(n^3). In practice it is much faster because most branches fail immediately.

Space: The recursion stack can be at most O(n) deep, one frame per term in the additive sequence. Each frame holds a constant amount of data plus the string s = str(c), which is O(log c) digits long. The total space is O(n).

Building blocks

This problem rests on two patterns that appear across many string and backtracking problems.

Backtracking with pruning

The outer loops try every possible pair of starting numbers. The leading-zero check prunes invalid candidates before any recursion happens. Inside check, the startswith comparison prunes the branch the moment the sequence diverges. This is the same prune-early philosophy that makes Combination Sum efficient: do not recurse into a subtree that is already guaranteed to fail.

The important difference from most backtracking problems is that here there is no explicit "unchoose" step. Once you call check(a, b, j), Python's call stack handles the backtracking for you. If check returns False, the outer loop just tries the next j value. The state is never mutated in place, so there is nothing to undo.

String-to-number splitting

A recurring pattern in string problems is converting substrings to integers and checking numeric properties. Here the critical skill is handling the split correctly: num[:i] gives the first segment, num[i:j] the second, and then you convert both to integers once and work with integers for all subsequent arithmetic. Converting to integers up front means the + operation is fast and exact, even for large numbers.

The reverse direction, going from integer back to string with str(c), lets you use startswith for a clean prefix check instead of slicing and comparing character by character.

Edge cases

Leading zeros: The string "100" should return False. The only valid split would need a=1 and b=0, giving c=1. The string after index 2 is "0", not "1". But a=10 and b=0 has a leading zero in b. So no split works. The string "010" with a leading zero in the entire input is technically rejected too, because any split of a from the front would use "0" as a single-digit number (valid) but then b would start with "1" and c = 0+1 = 1, so "0" at the remaining position would not match "1". The leading-zero guard correctly allows single-digit zeros.

Single-digit-only strings: The input must have at least 3 digits. With 2 digits, after picking a and b there is nothing left to verify the additive property (you need at least one more term). Constraints guarantee the input is long enough for a solution to be possible, but your code handles short strings naturally: the inner loop range(i+1, n) leaves no room for j < n, so no call to check is made and False is returned.

Very large numbers: Python integers are arbitrary precision, so adding two large numbers extracted from a long digit string is exact. There is no overflow to worry about. This is a meaningful advantage over C++ or Java solutions, which need long arithmetic or BigInteger. The str(c) conversion is also exact.

From understanding to recall

You understand the two-pointer split, the leading-zero check, and the recursive check function. You see how fixing a and b determines the rest of the sequence and why startswith is the right tool for prefix matching. But can you produce the complete solution from memory in under two minutes?

The details that trip people up under pressure: remembering to use continue (not break) in the leading-zero guard, passing the right start offset to startswith, and making sure the base case checks start == n rather than the sequence length. These are not conceptual problems. They are recall problems.

Spaced repetition fixes recall. You practice writing the split loop and the check function from scratch at increasing intervals until the structure is automatic. When a Fibonacci-string or additive-sequence variant shows up in your interview, you do not spend time rediscovering the approach. You just write it.

The additive number pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning each block individually and drilling it with spaced repetition is far more effective than grinding random problems and hoping the patterns surface when you need them.

Related posts

• Restore IP Addresses - Another string partitioning problem where you try all splits and validate each segment. Compare the pruning: IP addresses use a numeric range check, while Additive Number uses an exact-sum match.
• Combination Sum - Backtracking with pruning applied to numeric arrays. The prune-early strategy is the same, but the search space is over integer candidates rather than string positions.
• Word Break - Partitioning a string into valid segments, solved with dynamic programming rather than backtracking. A useful contrast for understanding when to enumerate all paths vs. cache overlapping subproblems.