Additive number

String Backtracking

33.5% acceptance

Jan 12, 2026

1275

827

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_additive_number(num: String) -> bool {
    fn is_valid(num1: &str, num2: &str, remaining: &str) -> bool {
      if num1.len() > 1 && num1.starts_with('0') || num2.len() > 1 && num2.starts_with('0') {
        return false;
      }
      
      let n1: u128 = num1.parse().unwrap_or(0);
      let n2: u128 = num2.parse().unwrap_or(0);
      let sum = (n1 + n2).to_string();
      
      if !remaining.starts_with(&sum) {
        return false;
      }
      
      if remaining == sum {
        return true;
      }
      
      is_valid(num2, &sum, &remaining[sum.len()..])
    }
    
    let n = num.len();
    for i in 1..=n/2 {
      for j in 1..=(n-i)/2 {
        if is_valid(&num[..i], &num[i..i+j], &num[i+j..]) {
          return true;
        }
      }
    }
    
    false
  }
}