Problem statement

A digit string is additive if it can be cut into a sequence of at least three numbers in which every number after the first two equals the sum of the two numbers just before it.

No number in the sequence may have a leading zero: 0 itself is allowed, but a piece such as 02 or 00 is not.

Given a digit string num, return true if it is additive.

Example 1

Input: num = "12122436"
Output: true
Explanation: 12 + 12 = 24 and 12 + 24 = 36.

Example 2

Input: num = "101"
Output: true
Explanation: 1 + 0 = 1.

Example 3

Input: num = "1023"
Output: false
Explanation: `1, 0, 2…` fails (1 + 0 ≠ 2), and any cut starting `1, 02` uses a leading zero.

Constraints

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

Follow-up: How would you handle inputs so long that the numbers overflow 64-bit integers?

Hints for Additive Number

1. Hint 1

   Once the first two numbers are fixed, the rest of the sequence is forced — each next number must be their sum.

2. Hint 2

   So try every length for the first number and every length for the second, then verify greedily.

3. Hint 3

   Reject first/second pieces with a leading zero, and skip pairs whose longer piece is longer than what is left of the string (their sum could not fit).

How to solve Additive Number

The first two numbers determine the whole sequence, so enumerate their lengths and check each candidate by repeatedly adding and matching the sum against the string.

Approach

1. For each length i of the first number and j of the second with i + j < n: stop growing i once it would start with a 0 and be longer than one digit; do the same for j with the digit at index i.
2. Skip the pair when max(i, j) > n − i − j: the third number is at least as long as the longer of the two, so it could not fit.
3. Set a, b to the two pieces and pos = i + j. While pos < n, compute c = a + b, check that num continues with the digits of c at pos, advance pos by its length, and shift a, b = b, c.
4. If a candidate reaches the end of the string, return true; if all fail, return false.

Why it works

Every valid split is found by exactly one choice of (i, j) because the remaining numbers are forced, and the verification follows that forced sequence. A computed sum never has a leading zero, so matching its digits respects the rule automatically. With at most 35 digits, the pruning keeps both starting pieces to 17 digits and every matched number stays below 10^17, so 64-bit integers suffice; for unbounded lengths, add the numbers as digit strings instead (the JavaScript and TypeScript solutions do this, since their numbers are only exact to 2^53).

Complexity

• Time — O(n^3) — O(n^2) starting pairs, each verified in O(n)
• Space — O(n)

Pitfalls

• A sequence needs at least three numbers — i + j must be strictly less than n.
• 0 is a valid number, so "000" and "101" are additive; only multi-digit pieces with a leading zero are invalid.
• Floating-point or 53-bit arithmetic silently loses digits on long inputs.

Reference solution

Python

def isAdditiveNumber(num: str) -> bool:
    n = len(num)
    for i in range(1, n):
        if num[0] == "0" and i > 1:
            break
        for j in range(1, n - i):
            if num[i] == "0" and j > 1:
                break
            if max(i, j) > n - i - j:
                continue
            a, b = int(num[:i]), int(num[i:i + j])
            pos = i + j
            ok = True
            while pos < n:
                c = a + b
                cs = str(c)
                if not num.startswith(cs, pos):
                    ok = False
                    break
                pos += len(cs)
                a, b = b, c
            if ok:
                return True
    return False

Java

public static boolean isAdditiveNumber(String num) {
    int n = num.length();
    for (int i = 1; i < n; i++) {
        if (num.charAt(0) == '0' && i > 1) break;
        for (int j = 1; i + j < n; j++) {
            if (num.charAt(i) == '0' && j > 1) break;
            if (Math.max(i, j) > n - i - j) continue;
            long a = Long.parseLong(num.substring(0, i));
            long b = Long.parseLong(num.substring(i, i + j));
            int pos = i + j;
            boolean ok = true;
            while (pos < n) {
                long c = a + b;
                String cs = Long.toString(c);
                if (!num.startsWith(cs, pos)) { ok = false; break; }
                pos += cs.length();
                a = b;
                b = c;
            }
            if (ok) return true;
        }
    }
    return false;
}

C++

bool isAdditiveNumber(string num) {
    int n = (int)num.size();
    for (int i = 1; i < n; i++) {
        if (num[0] == '0' && i > 1) break;
        for (int j = 1; i + j < n; j++) {
            if (num[i] == '0' && j > 1) break;
            if (max(i, j) > n - i - j) continue;
            long long a = stoll(num.substr(0, i)), b = stoll(num.substr(i, j));
            int pos = i + j;
            bool ok = true;
            while (pos < n) {
                long long c = a + b;
                string cs = to_string(c);
                if (num.substr(pos, cs.size()) != cs) { ok = false; break; }
                pos += (int)cs.size();
                a = b;
                b = c;
            }
            if (ok) return true;
        }
    }
    return false;
}

JavaScript

var isAdditiveNumber = function(num) {
    var n = num.length;
    var add = function(a, b) {
        var res = [], i = a.length - 1, j = b.length - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry > 0) {
            var sum = carry;
            if (i >= 0) sum += a.charCodeAt(i--) - 48;
            if (j >= 0) sum += b.charCodeAt(j--) - 48;
            res.push(sum % 10);
            carry = sum >= 10 ? 1 : 0;
        }
        return res.reverse().join("");
    };
    for (var i = 1; i < n; i++) {
        if (num[0] === "0" && i > 1) break;
        for (var j = 1; i + j < n; j++) {
            if (num[i] === "0" && j > 1) break;
            if (Math.max(i, j) > n - i - j) continue;
            var a = num.substring(0, i), b = num.substring(i, i + j), pos = i + j, ok = true;
            while (pos < n) {
                var c = add(a, b);
                if (num.substring(pos, pos + c.length) !== c) { ok = false; break; }
                pos += c.length;
                a = b;
                b = c;
            }
            if (ok) return true;
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium