Expression Add Operators - Solution & Explanation

Problem Overview: Given a numeric string and a target value, insert the operators +, -, and * between digits so the resulting expression evaluates exactly to the target. You must return all valid expressions while respecting operator precedence, especially multiplication.

Approach 1: Generate All Expressions + Evaluate (Brute Force) (Time: O(4^n * n), Space: O(n))

The most direct idea is to generate every possible expression by inserting an operator or choosing to extend the current number at each position. After constructing an expression string, evaluate it using a stack-based expression evaluator or a parser. This guarantees correctness but wastes time building many expressions that never match the target. Each expression evaluation takes O(n) time, and there are roughly 4^n operator placements (three operators or concatenation). This approach is useful conceptually because it clarifies the search space, but it performs redundant evaluation work.

Approach 2: Recursive Backtracking with Running Evaluation (Time: O(4^n), Space: O(n))

The efficient strategy builds expressions while simultaneously tracking their evaluated value. During recursion, maintain three pieces of state: the current index in the string, the current calculated value, and the last operand used. The last operand is necessary to correctly handle multiplication precedence. When adding *, subtract the previous operand from the running total and add the multiplied value instead (value - prev + prev * current). This simulates operator precedence without re-evaluating the entire expression.

At each recursion step, iterate over possible numeric substrings starting from the current index. Skip numbers with leading zeros (for example "05"). For the first number, start the expression without adding an operator. For subsequent numbers, recursively try +, -, and *. This pruning strategy ensures every partial expression maintains a correct running value, avoiding full expression parsing.

This technique combines backtracking with incremental evaluation over a string input while applying arithmetic rules from math. The recursion depth is at most n, and each step branches into multiple operator choices, giving exponential complexity but with minimal overhead.

Recommended for interviews: Recursive backtracking with running evaluation is the expected solution. Interviewers want to see how you manage operator precedence without re-parsing the expression each time. Starting with the brute force idea shows you understand the search space, but optimizing with a running total and previous operand demonstrates strong recursion and backtracking skills.