Expression add operators

Math String Backtracking

42.8% acceptance

Jan 12, 2026

3755

723

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value. Note that operands in the returned expressions should not contain leading zeros. Note that a number can contain multiple digits.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn add_operators(num: String, target: i32) -> Vec<String> {
    let mut result = Vec::new();
    let target = target as i64;
    Self::backtrack(&num, target, 0, 0, 0, String::new(), &mut result);
    result
  }
  
  fn backtrack(
    num: &str,
    target: i64,
    pos: usize,
    eval: i64,
    last: i64,
    expr: String,
    result: &mut Vec<String>
  ) {
    if pos == num.len() {
      if eval == target {
        result.push(expr);
      }
      return;
    }
    
    for i in pos..num.len() {
      // Skip numbers with leading zeros
      if i > pos && num.chars().nth(pos).unwrap() == '0' {
        break;
      }
      
      let num_str = &num[pos..=i];
      let num_val = num_str.parse::<i64>().unwrap();
      
      if pos == 0 {
        // First number, no operator before it
        Self::backtrack(num, target, i + 1, num_val, num_val, num_str.to_string(), result);
      } else {
        // Try addition
        Self::backtrack(
          num,
          target,
          i + 1,
          eval + num_val,
          num_val,
          format!("{}+{}", expr, num_str),
          result
        );
        
        // Try subtraction
        Self::backtrack(
          num,
          target,
          i + 1,
          eval - num_val,
          -num_val,
          format!("{}-{}", expr, num_str),
          result
        );
        
        // Try multiplication
        Self::backtrack(
          num,
          target,
          i + 1,
          eval - last + last * num_val,
          last * num_val,
          format!("{}*{}", expr, num_str),
          result
        );
      }
    }
  }
}