Expression Add Operators - Solution & Explanation

Problem Overview: Given a numeric string num and a target value, insert the operators +, -, or * between digits so the resulting expression evaluates exactly to the target. You cannot reorder digits and you cannot create numbers with leading zeros.

Approach 1: Brute Force Expression Generation (Exponential Time, O(4^n))

The straightforward idea is to generate every possible way to insert operators between digits and then evaluate each expression. For a string of length n, each gap can either place +, -, *, or no operator (concatenate digits). After generating an expression string, evaluate it using a parser or stack-based expression evaluator. This works but becomes expensive because the number of generated expressions grows exponentially and each evaluation costs additional time. Time complexity is roughly O(4^n * n) and space complexity is O(n) for recursion and expression storage.

Approach 2: Recursive Backtracking with Running Evaluation (O(3^n))

The optimized approach builds expressions while evaluating them on the fly using backtracking. Instead of constructing the full expression and evaluating later, track three values during recursion: the current index in the string, the running expression value, and the last operand used. The last operand is required to correctly handle multiplication because * has higher precedence. When you place *, subtract the previous operand from the running total and add the multiplied value.

At each step, extend the current number by taking one or more digits from the string. Skip numbers with leading zeros. Then recursively explore three choices: add (+), subtract (-), or multiply (*) with the current number. This avoids repeated parsing and keeps evaluation constant-time per step. Time complexity is approximately O(3^(n-1)) because each position branches into three operator choices. Space complexity is O(n) for the recursion stack and expression construction.

The algorithm relies heavily on controlled recursion and expression state management, making it a classic string search problem combined with math evaluation rules.

Recommended for interviews: Interviewers expect the recursive backtracking approach with running evaluation. The brute force idea shows you understand the search space, but the optimized method demonstrates control over recursion, operator precedence handling, and pruning invalid states like leading zeros.