Expression Add Operators - Solution & Explanation
Problem Statement
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.
Example 1:
Input: num = "123", target = 6 Output: ["1*2*3","1+2+3"] Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.
Example 2:
Input: num = "232", target = 8 Output: ["2*3+2","2+3*2"] Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.
Example 3:
Input: num = "3456237490", target = 9191 Output: [] Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.
Constraints:
1 <= num.length <= 10numconsists of only digits.-231 <= target <= 231 - 1
Approach Overview
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.
Approach 1: Recursive Backtracking
This approach involves using a recursive backtracking algorithm to explore all possible combinations of the operators between the digits. The algorithm tries to build expressions from the input string by considering each possible position for inserting an operator. It is essential to keep track of the current value of the expression, the previous operand (to handle multiplication correctly with due precedence), and the current path (the expression string being built).
We also need to ensure that no operand in the expression starts with a zero unless the operand is zero itself to avoid leading zero issues.
The C solution uses a helper function to recursively explore each possibility of operator insertion. It builds expressions by concatenating parts of the input string with operators and maintains an evaluation of the current expression state. The use of sprintf assists in building the expression path.
Complexity
Time Complexity: O(4^n), where n is the length of the input string 'num'. This accounts for the potential combinatorial explosion in choices of operations between each digit.
Space Complexity: O(n), due to the recursion call stack and the space needed to store the expressions.
Approach 2: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Backtracking | Time Complexity: O(4^n), where n is the length of the input string 'num'. This accounts for the potential combinatorial explosion in choices of operations between each digit. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Generate All Expressions + Evaluate | O(4^n * n) | O(n) | Good for understanding the full search space and verifying correctness conceptually |
| Recursive Backtracking with Running Evaluation | O(4^n) | O(n) | Best general solution for interviews; avoids repeated expression evaluation |
Video Solution
Expression Add Operators | Leetcode 282 | Live coding session 🔥🔥🔥 • Coding Decoded • 19,034 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Expression Add Operators easy or hard?
Expression Add Operators Python/Java solution
How to solve Expression Add Operators in O(n)?
What is the best approach for Expression Add Operators?
Is Expression Add Operators asked at Google/Amazon/Meta?
What data structure is used in Expression Add Operators?
What is the time complexity of Expression Add Operators?
Ready to solve this problem?
Practice Expression Add Operators with our built-in code editor and test cases.
Practice on FleetCode