Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
Move from brute-force thinking to an efficient approach using backtracking strategy.
An additive number is a string whose digits can form an additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
Given a string containing only digits, return true if it is an additive number or false otherwise.
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Example 1:
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
Example 2:
Input: "199100199" Output: true Explanation: The additive sequence is: 1, 99, 100, 199. 1 + 99 = 100, 99 + 100 = 199
Constraints:
1 <= num.length <= 35num consists only of digits.Follow up: How would you handle overflow for very large input integers?
Problem summary: An additive number is a string whose digits can form an additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two. Given a string containing only digits, return true if it is an additive number or false otherwise. Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Backtracking
"112358"
"199100199"
split-array-into-fibonacci-sequence)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #306: Additive Number
class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int i = 1; i < Math.min(n - 1, 19); ++i) {
for (int j = i + 1; j < Math.min(n, i + 19); ++j) {
if (i > 1 && num.charAt(0) == '0') {
break;
}
if (j - i > 1 && num.charAt(i) == '0') {
continue;
}
long a = Long.parseLong(num.substring(0, i));
long b = Long.parseLong(num.substring(i, j));
if (dfs(a, b, num.substring(j))) {
return true;
}
}
}
return false;
}
private boolean dfs(long a, long b, String num) {
if ("".equals(num)) {
return true;
}
if (a + b > 0 && num.charAt(0) == '0') {
return false;
}
for (int i = 1; i < Math.min(num.length() + 1, 19); ++i) {
if (a + b == Long.parseLong(num.substring(0, i))) {
if (dfs(b, a + b, num.substring(i))) {
return true;
}
}
}
return false;
}
}
// Accepted solution for LeetCode #306: Additive Number
func isAdditiveNumber(num string) bool {
n := len(num)
var dfs func(a, b int64, num string) bool
dfs = func(a, b int64, num string) bool {
if num == "" {
return true
}
if a+b > 0 && num[0] == '0' {
return false
}
for i := 1; i < min(len(num)+1, 19); i++ {
c, _ := strconv.ParseInt(num[:i], 10, 64)
if a+b == c {
if dfs(b, c, num[i:]) {
return true
}
}
}
return false
}
for i := 1; i < min(n-1, 19); i++ {
for j := i + 1; j < min(n, i+19); j++ {
if i > 1 && num[0] == '0' {
break
}
if j-i > 1 && num[i] == '0' {
continue
}
a, _ := strconv.ParseInt(num[:i], 10, 64)
b, _ := strconv.ParseInt(num[i:j], 10, 64)
if dfs(a, b, num[j:]) {
return true
}
}
}
return false
}
# Accepted solution for LeetCode #306: Additive Number
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
def dfs(a, b, num):
if not num:
return True
if a + b > 0 and num[0] == '0':
return False
for i in range(1, len(num) + 1):
if a + b == int(num[:i]):
if dfs(b, a + b, num[i:]):
return True
return False
n = len(num)
for i in range(1, n - 1):
for j in range(i + 1, n):
if i > 1 and num[0] == '0':
break
if j - i > 1 and num[i] == '0':
continue
if dfs(int(num[:i]), int(num[i:j]), num[j:]):
return True
return False
// Accepted solution for LeetCode #306: Additive Number
struct Solution;
impl Solution {
fn is_additive_number(num: String) -> bool {
let n = num.len();
let mut res = false;
let mut cur: Vec<u64> = vec![];
Self::dfs(0, &mut cur, &mut res, &num[0..n], n);
res
}
fn dfs(start: usize, cur: &mut Vec<u64>, valid: &mut bool, s: &str, n: usize) {
if start == n {
if cur.len() >= 3 {
*valid = true;
}
} else {
for i in start + 1..=n {
if &s[start..=start] == "0" && i - start > 1 {
return;
}
if let Ok(x) = s[start..i].parse::<u64>() {
let k = cur.len();
if k < 2 {
cur.push(x);
Self::dfs(i, cur, valid, s, n);
cur.pop();
} else {
if cur[k - 1] + cur[k - 2] == x {
cur.push(x);
Self::dfs(i, cur, valid, s, n);
cur.pop();
}
}
}
}
}
}
}
#[test]
fn test() {
let num = "112358".to_string();
let res = true;
assert_eq!(Solution::is_additive_number(num), res);
let num = "199100199".to_string();
let res = true;
assert_eq!(Solution::is_additive_number(num), res);
let num = "101".to_string();
let res = true;
assert_eq!(Solution::is_additive_number(num), res);
let num = "12012122436".to_string();
let res = true;
assert_eq!(Solution::is_additive_number(num), res);
let num = "121474836472147483648".to_string();
let res = true;
assert_eq!(Solution::is_additive_number(num), res);
}
// Accepted solution for LeetCode #306: Additive Number
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #306: Additive Number
// class Solution {
// public boolean isAdditiveNumber(String num) {
// int n = num.length();
// for (int i = 1; i < Math.min(n - 1, 19); ++i) {
// for (int j = i + 1; j < Math.min(n, i + 19); ++j) {
// if (i > 1 && num.charAt(0) == '0') {
// break;
// }
// if (j - i > 1 && num.charAt(i) == '0') {
// continue;
// }
// long a = Long.parseLong(num.substring(0, i));
// long b = Long.parseLong(num.substring(i, j));
// if (dfs(a, b, num.substring(j))) {
// return true;
// }
// }
// }
// return false;
// }
//
// private boolean dfs(long a, long b, String num) {
// if ("".equals(num)) {
// return true;
// }
// if (a + b > 0 && num.charAt(0) == '0') {
// return false;
// }
// for (int i = 1; i < Math.min(num.length() + 1, 19); ++i) {
// if (a + b == Long.parseLong(num.substring(0, i))) {
// if (dfs(b, a + b, num.substring(i))) {
// return true;
// }
// }
// }
// return false;
// }
// }
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.