Leetcode 282. Expression Add Operators
Asked at:
Meta
DESCRIPTION
Given a string of digits and a target integer, insert the binary operators +, -, and * between digits to form all valid expressions that evaluate to the target value. Operands cannot have leading zeros (except 0 itself). For example, given num = "123" and target = 6, valid expressions include "1+2+3" and "1*2*3", both evaluating to 6.
Input:
num = "123" target = 6
Output:
["1+2+3", "1*2*3"]
Explanation: Both expressions evaluate to 6. Note that "1*23" would give 23, not 6.
Constraints:
- 1 <= num.length <= 10
- num consists of only digits
- -2^31 <= target <= 2^31 - 1
Understanding the Problem
The core challenge is exploring all possible ways to split the digit string into operands and insert operators between them using DFS/backtracking. The critical complexity arises from handling multiplication precedence correctly: when we encounter *, we must "undo" the previous addition/subtraction and apply multiplication first. We need to track both the running total and the last operand value to handle this precedence. Additionally, we must validate that no operand has a leading zero (except 0 itself).
Building Intuition
A naive approach might evaluate each complete expression string using a parser, but this is inefficient and complex. A better approach uses DFS with running evaluation: maintain the current sum and the last added/subtracted value. When encountering *, subtract the last value from the sum, multiply it by the current operand, then add back the result. For example, in 2+3*4, when processing *4: current sum is 5, last value is 3, so compute 5 - 3 + 3*4 = 14.
This pattern appears in expression parsing, calculator implementations, and formula evaluation systems. Understanding how to handle operator precedence during recursive exploration is fundamental to building interpreters and compilers. The technique of tracking the "last operand" to retroactively adjust for precedence is a powerful trick applicable to many evaluation problems.
Common Pitfalls
Implementation
DFS Backtracking Framework
Implement the recursive exploration structure that tries all possible operand splits and operator insertions. At each position, decide how many digits to consume for the next operand (from 1 digit up to remaining length), then recursively try inserting +, -, or * before the next operand. Use a start index to track position in the string and build the expression path incrementally. For example, from "123" at position 0, try operands "1", "12", "123", then for each, recursively process the remainder with each operator.
def dfs(num, target, start, path, prev, curr, result):if start == len(num):if curr == target:result.append(path)returnfor i in range(start, len(num)):if i > start and num[start] == '0':breakoperand = int(num[start:i+1])op_str = num[start:i+1]if start == 0:dfs(num, target, i+1, op_str, operand, operand, result)else:dfs(num, target, i+1, path + '+' + op_str, operand, curr + operand, result)dfs(num, target, i+1, path + '-' + op_str, -operand, curr - operand, result)dfs(num, target, i+1, path + '*' + op_str, prev * operand, curr - prev + prev * operand, result)
Operator Precedence Handling
Implement the running evaluation logic that correctly handles multiplication precedence without building expression trees. Track two values: currentSum (the running total) and lastValue (the most recently added/subtracted operand). For + and -, simply update currentSum and set lastValue to the operand. For *, compute currentSum - lastValue + lastValue * currentOperand to retroactively apply multiplication. For example, building "2+3*4": after "2+3", currentSum=5 and lastValue=3; when adding "*4", compute 5 - 3 + 3*4 = 14.
# Operator precedence is already correctly handled in the DFS framework above.# The key logic:# - prev: tracks the last operand added/subtracted (lastValue)# - curr: tracks the running sum (currentSum)# For '+': curr + operand, prev = operand# For '-': curr - operand, prev = -operand# For '*': curr - prev + prev * operand (retroactively apply multiplication)def addExpressions(num, target):result = []if not num:return resultdfs(num, target, 0, "", 0, 0, result)return result
Operand Validation and Base Cases
Add validation logic to prevent invalid operands and handle termination conditions. Check for leading zeros: if the current operand starts with '0' and has more than one digit, break the loop (don't explore further lengths). Handle the first operand specially (no operator before it) by starting recursion with currentSum = operand and lastValue = operand. When reaching the end of the string (start == num.length), check if currentSum == target and add the expression to results. For example, reject "05" but accept "0" and "5" separately.
def dfs(num, target, start, path, prev, curr, result):if start == len(num):if curr == target:result.append(path)returnfor i in range(start, len(num)):if i > start and num[start] == '0':breakoperand = int(num[start:i+1])op_str = num[start:i+1]if start == 0:dfs(num, target, i+1, op_str, operand, operand, result)else:dfs(num, target, i+1, path + '+' + op_str, operand, curr + operand, result)dfs(num, target, i+1, path + '-' + op_str, -operand, curr - operand, result)dfs(num, target, i+1, path + '*' + op_str, prev * operand, curr - prev + prev * operand, result)
Complete Integration
Combine the DFS framework, precedence handling, and validation into a unified solution function. Create a main function addOperators(num, target) that initializes the result list and starts the DFS with the first operand (no operator prefix). The DFS function takes parameters: num, target, start (current position), currentSum, lastValue, path (expression string), and result (output list). This orchestrates the entire backtracking process: try all operand lengths from current position, validate each operand, recursively try all three operators, and collect valid expressions.
def addOperators(num, target):result = []if not num:return resultdfs(num, target, 0, "", 0, 0, result)return result
What We've Learned
- Pattern: Track `lastValue` to retroactively handle operator precedence during DFS without building parse trees
- Use Case: Expression evaluation, calculator implementations, formula parsers requiring operator precedence
- Optimization: Break early on leading zeros and integer overflow to prune invalid branches
- Technique: Separate handling for first operand (no operator) vs. subsequent operands (with operators) simplifies recursion logic
Problems to Practice
medium
This problem requires building valid expressions character-by-character using backtracking with constraints, similar to inserting operators between digits. Both problems involve exploring a solution space tree while maintaining validity rules and building strings incrementally.
medium
Like Expression Add Operators, this problem uses backtracking to find all combinations that reach a target value. Both require exploring different choices at each step, tracking accumulated results, and backtracking when paths don't lead to valid solutions.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early January, 2026
Meta
Senior
Late October, 2025
Meta
Mid-level
Mid May, 2025
Meta
Staff
Hello Interview Premium
Your account is free and you can post anonymously if you choose.