LeetCode 306: Additive Number Solution in Python – A Step-by-Step Guide

What Is LeetCode 306: Additive Number?

In LeetCode 306: Additive Number, you’re given a string of digits (e.g., "199100199"), and your task is to determine if it can be split into at least three numbers where each number (after the first two) is the sum of the two preceding ones. For example, "112358" works because it splits into [1, 1, 2, 3, 5, 8], where 1+1=2, 1+2=3, 2+3=5, and 3+5=8. Numbers can have multiple digits, but no leading zeros are allowed (unless the number is 0 itself). This problem tests your ability to handle string manipulation and sequence validation in Python.

Problem Statement

• Input: A string num containing only digits (0-9).
• Output: A boolean—True if the string is an additive number, False otherwise.
• Rules:
• The sequence must have at least 3 numbers.
• Each number must be the sum of the two before it.
• No leading zeros in numbers (e.g., "01" is invalid), except for "0" itself.

Constraints

• 1 <= num.length <= 35
• num contains only digits (0-9).

Examples

• Input: "112358"
• Output: True (Splits as [1, 1, 2, 3, 5, 8])
• Input: "199100199"
• Output: True (Splits as [1, 9, 9, 100, 199])
• Input: "123"
• Output: True (Splits as [1, 2, 3])
• Input: "1023"
• Output: False (No valid split)

Understanding the Problem: Finding an Additive Sequence

To solve LeetCode 306: Additive Number in Python, we need a function that takes a string and checks if it can be divided into a valid additive sequence. For "123", we could try [1, 2, 3] (1+2=3), which works. But for "1023", no split satisfies the rule—[1, 0, 2, 3] fails because 0+2≠3. A naive approach might try every possible split, but that’s inefficient. Instead, we’ll use:

• Best Solution (Backtracking): O(n³) time, O(n) space—smart and recursive.
• Alternative Solution (Iterative): O(n³) time, O(n) space—simpler but exhaustive.

Let’s start with the backtracking solution, explained in a beginner-friendly way.

Best Solution: Backtracking with String Validation

Why This Is the Best Solution

The backtracking approach is the top pick for LeetCode 306 because it’s both efficient and intuitive once you get the hang of it—running in O(n³) time (where n is the string length) and O(n) space (for recursion). It tries different splits for the first two numbers, then recursively checks if the rest of the string follows the additive rule. It’s like exploring a maze: pick a path, see if it works, and backtrack if it doesn’t. This method avoids unnecessary work by validating as it goes—perfect for this puzzle!

How It Works

Let’s think of this as building a sequence step-by-step:

• Step 1: Pick the First Two Numbers:
• Choose lengths for the first number (n1) and second number (n2).
• Extract them from the string, ensuring no leading zeros (unless the number is "0").
• Step 2: Validate the Rest:
• Compute the sum (n1 + n2).
• Check if the next part of the string starts with this sum.
• Recursively repeat: n2 becomes n1, sum becomes n2, and compute the next sum.
• Step 3: Backtrack:
• If a split fails (sum doesn’t match or string runs out), try a different n1 or n2 length.
• Step 4: Why It Works:
• Explores all valid splits efficiently.
• Stops early if a path fails.
• Handles multi-digit numbers naturally.

It’s like piecing together a number puzzle, one sum at a time!

Step-by-Step Example

Example: "112358"

• String: "112358", length = 6.
• Try n1 = "1" (len=1), n2 = "1" (len=1):
• Start = 2 (after "11").
• n1 = 1, n2 = 1, sum = 2.
• Next: "2358" starts with "2", remainder = "358".
• n1 = 1, n2 = 2, sum = 3.
• Next: "358" starts with "3", remainder = "58".
• n1 = 2, n2 = 3, sum = 5.
• Next: "58" starts with "5", remainder = "8".
• n1 = 3, n2 = 5, sum = 8.
• Next: "8" matches "8", remainder = "".
• Valid sequence: [1, 1, 2, 3, 5, 8].
• Return True.

No need to try more—first success wins!

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down for clarity:

Copy codeclass Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        def is_valid(num, start, n1, n2):
            # Base case: if we've used the whole string and have at least 3 numbers
            if start == len(num):
                return True

            # Compute the next number (n1 + n2)
            sum_val = str(int(n1) + int(n2))
            # Check if the remaining string starts with this sum
            if not num.startswith(sum_val, start):
                return False

            # Recurse with n2 as new n1, sum as new n2
            return is_valid(num, start + len(sum_val), n2, sum_val)

        n = len(num)
        # Try all possible lengths for first two numbers
        for i in range(1, n-1):  # Length of first number
            for j in range(i+1, n):  # Start of third number
                # Extract first number
                n1 = num[:i]
                if len(n1) > 1 and n1[0] == '0':  # No leading zeros
                    continue

                # Extract second number
                n2 = num[i:j]
                if len(n2) > 1 and n2[0] == '0':  # No leading zeros
                    continue

                # Check if remaining string forms a valid sequence
                if is_valid(num, j, n1, n2):
                    return True

        return False  # No valid split found

• Lines 3-14: is_valid helper:
• Takes the string, current position, and two numbers (n1, n2).
• If at end of string, return True (valid sequence).
• Compute sum, check if it matches the next part, recurse with updated n1, n2.
• Lines 17-18: Get string length, set up loops.
• Lines 19-31: Main logic:
• Loop over lengths for n1 and n2.
• Extract n1 and n2, skip if invalid (leading zeros).
• Call is_valid to check the rest.
• Return True on first success, False if all fail.
• Time Complexity: O(n³)—two loops (n²) and string operations (n).
• Space Complexity: O(n)—recursion stack.

This is like a detective following number clues—smart and recursive!

Alternative Solution: Iterative with Substring Checks

Why an Alternative Approach?

The iterative approach checks all possible splits for the first two numbers, then builds the sequence iteratively—O(n³) time, O(n) space. It’s simpler to follow—no recursion—but still thorough, making it a good learning tool for beginners.

How It Works

Think of this as assembling the sequence manually:

• Step 1: Pick n1 and n2 lengths.
• Step 2: Build the sequence by adding n1 + n2, checking the string.
• Step 3: Continue until the string is used or fails.
• Step 4: Try all n1, n2 pairs.

It’s like laying out number blocks one by one!

Step-by-Step Example

Example: "123"

• Try n1 = "1", n2 = "2":
• Sequence: [1, 2], next = 1+2 = 3.
• String left: "3", matches, used all string.
• Valid: [1, 2, 3].
• Return True.

Code for Iterative Approach

Copy codeclass Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)
        for i in range(1, n-1):
            for j in range(i+1, n):
                n1 = num[:i]
                if len(n1) > 1 and n1[0] == '0':
                    continue
                n2 = num[i:j]
                if len(n2) > 1 and n2[0] == '0':
                    continue

                # Build sequence iteratively
                first = int(n1)
                second = int(n2)
                k = j  # Start of next number
                while k < n:
                    third = first + second
                    third_str = str(third)
                    if not num.startswith(third_str, k):
                        break
                    k += len(third_str)
                    first, second = second, third
                if k == n:  # Used whole string
                    return True

        return False

• Time Complexity: O(n³)—two loops and string checks.
• Space Complexity: O(n)—for string storage.

It’s a steady, step-by-step builder!

Comparing the Two Solutions

• Backtracking (Best):
• Pros: O(n³) time, O(n) space, elegant recursion.
• Cons: Recursion might confuse beginners.
• Iterative (Alternative):
• Pros: O(n³) time, O(n) space, straightforward.
• Cons: Slightly more verbose.

Backtracking edges out for elegance.

Additional Examples and Edge Cases

• "123": True ([1, 2, 3]).
• "1023": False (No valid split).
• "000": True ([0, 0, 0]).

Both handle these well.

Complexity Breakdown

• Backtracking: Time O(n³), Space O(n).
• Iterative: Time O(n³), Space O(n).

Similar performance, different styles.

Key Takeaways

• Backtracking: Explore and retreat—clever!
• Iterative: Build and check—simple!
• Strings: Python slicing is your friend—see [Python Basics](/python/basics).
• Sequences: Additive rules are fun.

Final Thoughts: Crack the Additive Code

LeetCode 306: Additive Number in Python is a delightful string-splitting challenge. Backtracking offers a sleek solution, while the iterative method keeps it grounded. Want more string puzzles? Check out LeetCode 139: Word Break or LeetCode 647: Palindromic Substrings. Ready to test your skills? Head to Solve LeetCode 306 on LeetCode and uncover those additive sequences today!