306. Additive Number


Problem Description

The problem asks us to determine if a given string of digits represents an 'additive number'. An additive number is defined as a sequence of at least three numbers where each number, starting from the third one, is the sum of its two immediate predecessors. The challenge is to check if such a partition of the digit sequence into an additive sequence is possible.

For example, in the additive sequence 112358, 1, 1, and 2 are the first three elements, and each subsequent element is the sum of the previous two (i.e., 3 is 1 + 2, 5 is 2 + 3, and so forth).

A few rules apply to the number sequence:

  • The sequence must contain at least three numbers.
  • Leading zeros are not allowed. For instance, 02 as a number is not valid, which means a sequence like 1, 02, 3 is invalid.

Considering these rules, we need to check every possible pair of the first two numbers and see if we can build a valid additive sequence for the entire string.

Intuition

To solve this problem, we'll employ a backtracking approach with a depth-first search (DFS) algorithm, which will try all possible splits of the initial string into numbers that could form an additive sequence.

The approach is as follows:

  1. Try all pairs of initial numbers 'a' and 'b', which could be the start of an additive sequence.
  2. Recursively check if the rest of the string can form a continuation of the sequence where the third number, and each thereafter, is the sum of the previous two.
  3. If at any depth the next number in the sequence cannot be formed from a sum of the previous two, backtrack and try a different split.

To avoid leading zeros, we check if the current number being formed is greater than zero and starts with a zero digit. If so, we immediately return False for that path.

The DFS function (dfs) handles the backtracking. It takes two numbers 'a' and 'b' and the remaining string as arguments. It then tries to form the next number, which should be equal to the sum of 'a' and 'b'. If it finds such a number, it proceeds by making a recursive call with 'b', the sum of 'a' and 'b' as the new pair, and the remaining string (after removing the used number). If the string is entirely used, and all numbers followed the additive sequence, it returns True. If no valid sequence is found throughout the entire for-loop, it returns False.

In the solution code, the main function first iterates through all possible pairs of the first two numbers using two nested for-loops. Then it applies the dfs to check if the rest of the string can form an additive sequence starting with these two numbers. If the dfs function returns True at any point, the function concludes that a valid additive sequence is possible and returns True. If no such sequence is found, it returns False.

Solution Approach

The implementation of the solution leverages recursion for backtracking and simple iteration to try all possible initial pairs of numbers that might start an additive sequence. Below, the implementation details are elaborated:

  1. Outer Loops: There are two nested loops that iterate over the input string num to choose the first two numbers 'a' and 'b'. The first loop (starting with for i in range(1, n - 1)) selects the ending position for the first number 'a', while the second loop (starting with for j in range(i + 1, n)) selects the ending position for the second number 'b'.

  2. Leading Zero Check for 'a' and 'b': Before using the chosen numbers to attempt building an additive sequence, we check for leading zeros to avoid invalid sequences. If 'a' is chosen to have a length greater than 1 and starts with '0', the loop is broken, as that would not qualify for a valid number. Similarly, if 'b' starts with '0', the current iteration is skipped.

  3. Depth-First Search (DFS) Function: The dfs(a, b, num) function serves as the main recursive component of the solution. It takes two integers a and b from the previously chosen splits and the remaining part of the string as num.

    • Base Case: If num is empty, it means we've reached the end of the input string, and the sequence followed the additive property up to this point. Thus, it returns True.

    • Leading Zero Check for the Next Number: Since the next number in the sequence cannot start with a zero unless it is zero itself, we immediately return False if num starts with '0', but the expected sum of 'a' and 'b' is greater than zero.

    • Next Number Formation: The DFS function enters into a for-loop attempting to create the next number in the sequence from the current string num. It does this by slicing the string from the start to an index i, converting it to an integer, and checking if it equals the sum of 'a' and 'b'.

    • Recursive Depth-First Search: Upon finding the correct next number, the function recurses by calling dfs(b, a + b, num[i:]), where b and a + b become the new previous two numbers, and num[i:] is the remaining string. If this recursive call eventually leads to the base case returning True, the current dfs also returns True. If not, it continues to try other possible splits in the for-loop.

  4. Running DFS from the Main Function: After calling dfs(int(num[:i]), int(num[i:j]), num[j:]) with the initial 'a' and 'b' and the rest of the string, if ever the function returns True, it means a valid sequence has been formed, and the solution returns True. If none of the initial pairs 'a' and 'b' lead to a valid sequence, the function concludes it is not an additive number and returns False.

This solution capitalizes on the ability of DFS to explore all possible valid sequences exhaustively, with backtracking ensuring that once an invalid sequence is identified, it reverts to the previous state to try alternative paths. The careful check for leading zeros is particular to the problem statement, as such sequences are considered invalid.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach using a small example: the string 12122436.

Step 1: Outer Loops for Initial Number Selection We start by choosing the first two numbers 'a' and 'b' from the string:

  • First, we select 'a' as 1 (the first number in the string) and 'b' as 2 (the second number in the string). This gives us potential starting numbers of the sequence.

Step 2: Leading Zero Check

  • We check that neither 'a' nor 'b' start with a zero since they are single digits in this case, so we proceed.

Step 3: Applying the DFS Function Now we use the recursive DFS function to find the next number in the sequence:

  • The sum of 'a' (1) and 'b' (2) is 3. We look for a 3 in the remaining string 122436. We find it starting just after 'b', which looks promising.

  • We call dfs(2, 3, "2436"). Now 'b' is 2, the sum is 3, and we have reduced the problem to a new string.

Step 4: Continuing Depth-First Search We continue the depth-first search with the new parameters:

  • The sum of the new 'a' (2) and 'b' (3) is 5. We look for a 5 in the remaining string 2436. We find it starting at index 1.

  • We call dfs(3, 5, "436") and check for the next number in the sequence, which should be the sum of 3 and 5, which is 8.

  • We search for 8 in "436". It is not present; hence this path does not lead to a solution.

Step 5: Backtracking Since we cannot find an 8 following the 3 and 5, we backtrack and try the next possible starting numbers:

  • We return to our first pair and select a different 'b': now let's take 1 as 'a' and 21 as 'b'.

    • The sum we're looking for is 22 (sum of 1 and 21), which is present in the remaining string 22436.

    • We call dfs(21, 22, "436") and check for the next number, which should be 43 (sum of 21 and 22).

    • We find 43 in "436", so we continue with dfs(22, 43, "6").

  • Now, we look for the sum of 22 and 43, which is 65, but since our remaining string is just "6", this is not possible. So we backtrack again.

Step 6: Trying New Pairs Again Finally, we try 12 as 'a' and 12 as 'b':

  • We look for 24 (sum of 12 and 12) in the remaining string 2436 and find it.

  • This process continues recursively: dfs(12, 24, "36"), then looking for 36 (sum of 12 and 24), and finding it in "36".

  • We call dfs(24, 36, ""). The string is empty, and we've maintained the additive sequence, so we return True.

In this example, the string 12122436 fulfills the property of being an additive number, with the sequence being 12, 12, 24, 36. The outer loops and DFS have successfully found a valid additive sequence, so the solution would return True.

Python Solution

1class Solution:
2    def is_additive_number(self, num: str) -> bool:
3        # Helper function to perform DFS to check if the number is additive
4        def dfs(first, second, remaining):
5            # Base condition: if no remaining digits, return True
6            if not remaining:
7                return True
8            # Lead zero condition not allowed unless the number is 0
9            if first + second > 0 and remaining[0] == '0':
10                return False
11            # Try to find the next number which should be the sum of the last two
12            for i in range(1, len(remaining) + 1):
13                # Check if the current prefix is the sum of the last two numbers
14                if first + second == int(remaining[:i]):
15                    # Recurse with the second as first and current prefix as second
16                    if dfs(second, first + second, remaining[i:]):
17                        return True
18            # Return False if no valid continuation is found
19            return False
20
21        n = len(num)
22        # Try every combination of the first two numbers to start the sequence
23        for i in range(1, n - 1):
24            for j in range(i + 1, n):
25                # No leading zero allowed for a number unless it is 0
26                if i > 1 and num[0] == '0':
27                    break
28                # Second number cannot start with a leading zero unless it is 0
29                if j - i > 1 and num[i] == '0':
30                    continue
31                # Check recursively if the remaining string is an additive sequence starting with these two numbers
32                if dfs(int(num[:i]), int(num[i:j]), num[j:]):
33                    return True
34        # If no additive sequence is found, return False
35        return False
36

Java Solution

1class Solution {
2  
3    // Main function to check if a number is an additive number
4    public boolean isAdditiveNumber(String num) {
5        int n = num.length();
6      
7        // The first number should be less than n - 1 digits and not have leading zeroes
8        // Limit to 19 digits to avoid parsing numbers larger than Long.MAX_VALUE
9        for (int firstNumEndIndex = 1; firstNumEndIndex < Math.min(n - 1, 19); ++firstNumEndIndex) {
10            // The second number should start after the first and also avoid leading zeroes
11            for (int secondNumStartIndex = firstNumEndIndex + 1; secondNumStartIndex < Math.min(n, firstNumEndIndex + 19); ++secondNumStartIndex) {
12                if (firstNumEndIndex > 1 && num.charAt(0) == '0') {
13                    // Exclude numbers with leading zeroes
14                    break;
15                }
16                if (secondNumStartIndex - firstNumEndIndex > 1 && num.charAt(firstNumEndIndex) == '0') {
17                    continue; // Skip if second number has leading zeroes
18                }
19                long firstNum = Long.parseLong(num.substring(0, firstNumEndIndex));
20                long secondNum = Long.parseLong(num.substring(firstNumEndIndex, secondNumStartIndex));
21                // Use a helper function to recursively check the rest of the sequence
22                if (isAdditiveSequence(firstNum, secondNum, num.substring(secondNumStartIndex))) {
23                    return true;
24                }
25            }
26        }
27        return false;
28    }
29
30    // Helper function to recursively check the additive sequence
31    private boolean isAdditiveSequence(long firstNum, long secondNum, String remainingNum) {
32        // If there's no more characters left to check, we've found an additive sequence
33        if ("".equals(remainingNum)) {
34            return true;
35        }
36        // Exclude checks where the next number starts with '0' unless it's just '0'
37        if (firstNum + secondNum > 0 && remainingNum.charAt(0) == '0') {
38            return false;
39        }
40      
41        // Loop through potential next numbers in the sequence
42        for (int nextNumEndIndex = 1; nextNumEndIndex < Math.min(remainingNum.length() + 1, 19); ++nextNumEndIndex) {
43            long sum = firstNum + secondNum;
44            String sumStr = remainingNum.substring(0, nextNumEndIndex);
45            // Parse the next number and compare it against the sum
46            if (sum == Long.parseLong(sumStr)) {
47                // If the sum matches the next number, continue checking the sequence
48                if (isAdditiveSequence(secondNum, sum, remainingNum.substring(nextNumEndIndex))) {
49                    return true;
50                }
51            }
52        }
53        // If no valid additive sequence is found
54        return false;
55    }
56}
57

C++ Solution

1class Solution {
2public:
3    // Function to determine if a given string is an additive number
4    bool isAdditiveNumber(string num) {
5        int n = num.size();
6
7        // Loop through the string with two pointers to split the string into 3 parts
8        for (int i = 1; i < min(n - 1, 19); ++i) { // first part [0, i)
9            // The second number starts from i and goes up to a max of 18 digits ahead
10            for (int j = i + 1; j < min(n, i + 19); ++j) { // second part [i, j)
11                // Avoid unnecessary work when the first number has a leading zero and length > 1
12                if (i > 1 && num[0] == '0') break;
13                // Skip when the second number has a leading zero and length > 1
14                if (j - i > 1 && num[i] == '0') continue;
15
16                // Convert the first and second part of the string to numbers
17                auto firstNum = stoll(num.substr(0, i));
18                auto secondNum = stoll(num.substr(i, j - i));
19
20                // Check if the remaining string is a valid sequence starting with firstNum and secondNum
21                if (dfs(firstNum, secondNum, num.substr(j))) return true;
22            }
23        }
24        // If no valid sequence is found, return false
25        return false;
26    }
27
28    // Helper function to recursively check if the string forms a valid additive sequence
29    bool dfs(long long firstNum, long long secondNum, string remaining) {
30        // If all the string has been used, it's a valid sequence
31        if (remaining == "") return true;
32
33        // If the sum leads to a number with leading zeros and the number is not zero, return false
34        if (firstNum + secondNum > 0 && remaining[0] == '0') return false;
35
36        // Iterate through the remaining string to find the next valid number in the sequence
37        for (int i = 1; i < min((int) remaining.size() + 1, 19); ++i) {
38            // Check if the sum of the first two numbers equals the next part of the string converted to a number
39            if (firstNum + secondNum == stoll(remaining.substr(0, i))) {
40                // Recursively check the rest of the string using the second and third numbers as the next pair
41                if (dfs(secondNum, firstNum + secondNum, remaining.substr(i)))
42                    return true;
43            }
44        }
45        // If no valid continuation is found, return false
46        return false;
47    }
48};
49

Typescript Solution

1// Function to determine if a given string is an additive number
2function isAdditiveNumber(num: string): boolean {
3    const n: number = num.length;
4
5    // Loop through the string with two pointers to split the string into 3 parts
6    for (let i = 1; i < Math.min(n - 1, 19); ++i) { // first part [0, i)
7        for (let j = i + 1; j < Math.min(n, i + 19); ++j) { // second part [i, j)
8            // Avoid unnecessary work when the first number has a leading zero and length > 1
9            if (i > 1 && num[0] === '0') break;
10            // Skip when the second number has a leading zero and length > 1
11            if (j - i > 1 && num[i] === '0') continue;
12
13            // Convert the first and second part of the string to BigInt numbers
14            const firstNum: BigInt = BigInt(num.substring(0, i));
15            const secondNum: BigInt = BigInt(num.substring(i, j - i));
16
17            // Check if the remaining string is a valid sequence starting with firstNum and secondNum
18            if (dfs(firstNum, secondNum, num.substring(j))) return true;
19        }
20    }
21    // If no valid sequence is found, return false
22    return false;
23}
24
25// Helper function to recursively check if the string forms a valid additive sequence
26function dfs(firstNum: BigInt, secondNum: BigInt, remaining: string): boolean {
27    // If all the string has been used, it's a valid sequence
28    if (remaining === "") return true;
29
30    // If the sum leads to a number with leading zeros and the number is not zero, return false
31    if (firstNum + secondNum > BigInt(0) && remaining[0] === '0') return false;
32
33    // Iterate through the remaining string to find the next valid number in the sequence
34    for (let i = 1; i < Math.min(remaining.length + 1, 19); ++i) {
35        // Check if the sum of the first two numbers equals the next part of the string converted to a BigInt
36        if (firstNum + secondNum === BigInt(remaining.substring(0, i))) {
37            // Recursively check the rest of the string using the second and third numbers as the next pair
38            if (dfs(secondNum, firstNum + secondNum, remaining.substring(i)))
39                return true;
40        }
41    }
42    // If no valid continuation is found, return false
43    return false;
44}
45

Time and Space Complexity

The given Python function isAdditiveNumber checks whether a string represents an additive number, where each digit or pair of digits forms a sequence such that each number (starting with the third) is the sum of the preceding two.

Time Complexity

The main function uses backtracking, where two nested loops determine the first two numbers and a recursive helper function (dfs) continues the sequence. Here is the detailed time complexity breakdown:

  1. Two nested loops:

    • The outer loop runs (n-1) times, where n is the length of the input string because we need at least one digit for the last number in the sequence.
    • The inner loop starts from i+1 and runs till n, making up to (n-i) iterations.
    • Each iteration of the inner loop calls the dfs function.
  2. The dfs function:

    • This is a recursive function that can potentially be called up to n times, where n is the remaining length of the string.
    • In the worst case, we could be trying every possible split of the remainder of the string, resulting in a time complexity that has an upper bound of O(2^n), since each position in the input could represent a different branch in the recursive call tree.

Putting it all together, the total time complexity of the function is:

  • O((n-1) * (n-i) * 2^n) which simplifies to O(n^2 * 2^n), since n-i is less than n.

Space Complexity

The space complexity of the code is affected by the depth of the recursion stack and the space needed to store the inputs for each recursive call:

  1. Recursion Stack Depth:

    • In the worst case, the recursion could go n levels deep, where n is the length of the input string.
  2. Space for Inputs in Recursive Calls:

    • For every call to dfs, we make a new substring and integer conversions. However, since the substrings created in Python are views on the original string without copying, the space consumed by substrings is not a major concern.
    • The space for integer variables a and b, each of which is a result of a substring conversion, is minor and constant (O(1)).

Considering the above points, the space complexity is mainly governed by the recursion stack depth, which is O(n).

Putting it all together, the space complexity of the function is O(n) due to recursion depth.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫