> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Additive Number Python Solution with Tests

> Tested Python solution for LeetCode 306 with 24 pytest cases. Generate a practice environment with lcpy.

LeetCode 306, [Medium](/catalog/medium). Topics: [String](/catalog/topics/string), [Backtracking](/catalog/topics/backtracking). [View on LeetCode](https://leetcode.com/problems/additive-number/description/).

Generate this problem as a practice environment: tested reference solution, 24 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 306   # by problem number
lcpy gen -s additive_number   # by problem name
```

## Problem

An \<strong>additive number\</strong> is a string whose digits can form an \<strong>additive sequence\</strong>.

\<p>A valid \<strong>additive sequence\</strong> should contain \<strong>at least\</strong> three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.\</p>

\<p>Given a string containing only digits, return \<code>true\</code> if it is an \<strong>additive number\</strong> or \<code>false\</code> otherwise.\</p>

### Examples

```
Input: "112358"
Output: true
Explanation: 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
```

```
Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
```

```
Input: "1023"
Output: false
Explanation: No valid additive sequence exists.
```

### Constraints

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

\<p>\<strong>Note:\</strong> Numbers in the additive sequence \<strong>cannot\</strong> have leading zeros, so sequence \<code>1, 2, 03\</code> or \<code>1, 02, 3\</code> is invalid.\</p>

**Follow up:** How would you handle overflow for very large input integers?

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/additive_number/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/additive_number/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^3) - n^2 first-two-number splits, each validated in O(n) steps
    # Space: O(n)
    def is_additive_number(self, num: str) -> bool:
        n = len(num)

        def valid(a_end: int, b_end: int) -> bool:
            first, second = num[:a_end], num[a_end:b_end]
            if len(first) > 1 and first[0] == "0":
                return False
            if len(second) > 1 and second[0] == "0":
                return False
            prev, cur = int(first), int(second)
            end = b_end
            while end < n:
                total = prev + cur
                total_str = str(total)
                if not num.startswith(total_str, end):
                    return False
                end += len(total_str)
                prev, cur = cur, total
            return True

        for a_end in range(1, n - 1):
            for b_end in range(a_end + 1, n):
                if valid(a_end, b_end):
                    return True
        return False
```

## Complexity

| Time | Space |
| - | - |
| O(n^3) - n^2 first-two-number splits, each validated in O(n) steps | O(n) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.