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.

Learn more about Backtracking patterns.

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.

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.

Solution Implementation

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.

Learn more about how to find time and space complexity quickly using problem constraints.