Additive number sequence

Determine if a numeric string can be split into an additive sequence following Fibonacci-like rules.

strings parsing fibonacci backtracking validation

An additive number is a string of digits that can be split into a sequence of non-negative integers `seq` (length at least 3) such that:
- `seq[0] + seq[1] == seq[2]`, `seq[1] + seq[2] == seq[3]`, and so on.
- No number in the sequence has a leading zero, except the single digit `0` itself.

Your task is to implement a function `is_additive_number(num: str) -> bool` that returns `True` if the given string `num` can form a valid additive sequence, and `False` otherwise.

Details:
- `num` consists only of digits ('0'-'9').
- The entire string must be consumed by the sequence.
- You may choose any starting two numbers, as long as the resulting sequence satisfies the additive property and has length at least 3.
- Numbers must not be too large: each number can be up to 20 digits; assume input length ≤ 20, so numbers will fit within standard integer limits (Python ints handle them).
- Leading zeros are not allowed in any number of the sequence except the number `0` itself. This means the first two numbers cannot have leading zeros (except if they are exactly `0`), and subsequent numbers should also not have leading zeros when generated.

Examples:
- `"112358"` → `True` because `1, 1, 2, 3, 5, 8` (1+1=2, 1+2=3, 2+3=5, 3+5=8).
- `"199100199"` → `True` because `1, 99, 100, 199` (1+99=100, 99+100=199).
- `"1023"` → `False` because `1, 02, 3` invalid (leading zero) and `10, 2, 3` fails (10+2≠3), etc.
- `"101"` → `True` because `1, 0, 1` (1+0=1).
- `"000"` → `True` because `0, 0, 0` (0+0=0).
- `"0123"` → `False` because the first number cannot have leading zero, and no other partition produces a valid sequence.

Implement the function accordingly.

Constraints

- `1 <= len(num) <= 20`
- `num` contains only digits.
- Expected time complexity: O(n^3) worst-case where n is length of `num`. Acceptable for n ≤ 20.
- Return a boolean.

Example

>>> is_additive_number("112358")
True
>>> is_additive_number("199100199")
True
>>> is_additive_number("1023")
False
>>> is_additive_number("101")
True
>>> is_additive_number("000")
True
>>> is_additive_number("0123")
False

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Try all possible lengths for the first two numbers, but skip numbers with leading zeros unless they are exactly '0'.

Once you have the first two numbers, generate the rest of the sequence and check if it builds up exactly to the end of the string.

To avoid huge numbers, you can stop early if the concatenation length exceeds the remaining length.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.