Additive Number - Video Solutions

Problem Overview: You are given a numeric string num. The task is to determine whether it can form an additive sequence. In an additive sequence, every number (starting from the third) equals the sum of the previous two. Numbers cannot have leading zeros unless the number itself is 0.

Approach 1: Recursive Backtracking with Early Termination (O(n^3) time, O(n) space)

This approach tries all possible ways to split the first two numbers in the string, then recursively verifies whether the remaining string follows the additive rule. Start by choosing indices i and j to define the first two numbers. Convert them to integers (or use string-based addition to avoid overflow), compute their sum, and check if the next part of the string begins with that value. If it matches, continue the process recursively with the new pair. Early termination happens when a generated sum does not match the next substring, which prunes large parts of the search tree. The method naturally fits a backtracking pattern because you explore candidate splits and abandon invalid sequences quickly. Parsing and substring comparisons lead to O(n^3) time in the worst case, while recursion depth and substring storage require O(n) space.

Approach 2: Iterative Approach with Two Pointers (O(n^3) time, O(1) space)

This approach removes recursion and checks sequences iteratively. First, iterate over all possible splits for the first and second numbers using two pointers. After fixing these two values, simulate the additive sequence by repeatedly computing their sum and checking if the next substring matches it. If it matches, move the pointers forward and continue with the new pair. If any mismatch occurs, break early and try another split. Since you only track a few indices and temporary values, the extra space stays at O(1). However, generating candidate pairs and validating the remaining substring still leads to O(n^3) time complexity in the worst case. The approach mainly relies on careful string manipulation and controlled pointer movement similar to patterns used in two pointers problems.

Recommended for interviews: The recursive backtracking solution is usually preferred in interviews because it clearly expresses the search space and shows that you can prune invalid paths early. Interviewers expect you to handle leading zeros, large number addition, and substring validation carefully. The iterative version demonstrates strong control over pointer logic and space optimization. Showing the brute-force split idea first, then refining it with early termination, signals strong problem-solving skills.