#306

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Additive Number

Additive Number is solved by trying the first two splits, then pruning aggressively while verifying each required sum in order.

string backtracking

Problem Statement

You are given a digit string and need to decide whether it can be partitioned into an additive sequence. In this sequence, there must be at least three numbers, and every number after the first two must equal the sum of the previous two numbers when read in order from the string.

The interview challenge in Additive Number is not just generating splits, but validating them under string constraints. A candidate sequence becomes invalid immediately if a number has an illegal leading zero or if the next expected sum does not align with the next substring, so the search must prune early instead of exploring every partition.

Examples

Example 1

Input: "112358"

Output: true

The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2

Input: "199100199"

Output: true

The additive sequence is: 1, 99, 100, 199. 1 + 99 = 100, 99 + 100 = 199

Constraints

1 <= num.length <= 35
num consists only of digits.

Solution Approach

Choose the first two numbers carefully

Start by enumerating the end of the first number and the end of the second number. Those two choices fully determine the rest of the sequence, so Additive Number becomes a validation problem after the initial split. Prune any choice where a multi-digit number starts with 0, because that failure mode appears constantly in this problem.

Backtrack by matching the next required sum

Once the first two numbers are fixed, compute their sum and compare it to the next part of the string. If the string at the current index begins with that exact sum, advance and continue with the last two numbers shifted forward. If it does not match exactly, stop that branch immediately, because no later split can repair a wrong additive step.

Use string-aware validation to avoid numeric traps

Since num.length can reach 35, many implementations avoid relying on fixed-width integers and compare sums as strings. Whether you use big integers or manual string addition, the important trade-off in Additive Number is correctness on long substrings versus code simplicity. The algorithm stays the same: deterministic continuation after two starting choices, with pruning on mismatch.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

If the first number ends at i and the second ends at j, there are O(n^2) starting split choices to test. For each choice, validation can scan forward through the remaining string, so a practical bound is often described as O(n^3) with string-based checks, though pruning usually cuts many branches early. Space is O(n) in the worst case if recursion or string-sum construction is used, and closer to O(1) auxiliary space if validation is iterative aside from temporary sum strings.

What Interviewers Usually Probe

They want you to notice that after picking the first two numbers, the rest of Additive Number is forced rather than freely partitioned.
They are checking whether you catch the leading-zero rule for both starting numbers and later generated values.
They expect pruning logic, not brute-force partition generation across the whole string.

Common Pitfalls or Variants

Common pitfalls

Allowing values like "01" or "00" as multi-digit tokens, which makes invalid branches look valid.
Using 32-bit or 64-bit arithmetic blindly, which can break Additive Number on longer substrings near the length limit.
Continuing search after the expected sum fails to match the next substring, instead of pruning that branch immediately.

Follow-up variants

Return the actual additive sequence instead of a boolean, which means storing the chosen numbers along the successful path.
Count how many valid additive decompositions exist, which removes the early exit and makes pruning even more important.
Implement the same Additive Number logic with manual string addition to avoid overflow-dependent solutions.

FAQ

What is the main pattern behind Additive Number?

The core pattern is backtracking search with pruning. You try possible first and second numbers, then the rest of the sequence is forced by repeated sum matching, so the real skill is cutting invalid branches early.

Why is Additive Number usually solved by fixing the first two numbers?

Because every later value must equal the sum of the previous two, choosing the first pair determines the entire remaining path. That turns the problem from general partitioning into deterministic verification with pruning.

How do leading zeroes affect this problem?

A single digit "0" is valid, but any multi-digit number starting with 0 is invalid. Missing this rule is one of the most common correctness bugs in Additive Number.

Do I need BigInt or manual string addition for LeetCode 306?

You can use a wider numeric type where available, but string-based addition is safer because the input length can exceed fixed-width integer comfort zones. The important part is preserving exact sum matching against the next substring.

Why is brute force partitioning the wrong mindset here?

Brute force treats every cut as independent, but Additive Number has a strong dependency: after two numbers, every next chunk is predetermined. Good solutions exploit that structure and prune the moment the expected sum does not match.

terminal

Solution

Solution 1

#### Python3

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        def dfs(a, b, num):
            if not num:
                return True
            if a + b > 0 and num[0] == '0':
                return False
            for i in range(1, len(num) + 1):
                if a + b == int(num[:i]):
                    if dfs(b, a + b, num[i:]):
                        return True
            return False

        n = len(num)
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                if i > 1 and num[0] == '0':
                    break
                if j - i > 1 and num[i] == '0':
                    continue
                if dfs(int(num[:i]), int(num[i:j]), num[j:]):
                    return True
        return False

Continue Practicing

#301 remove invalid parentheses #282 expression add operators #257 binary tree paths