LeetCode 282 - Expression Add Operators
The problem gives us a numeric string num and an integer target. We must insert binary operators, specifically '+', '-', and '', between the digits of the string so that the resulting mathematical expression evaluates exactly to target.
Difficulty: 🔴 Hard
Topics: Math, String, Backtracking
Solution
Problem Understanding
The problem gives us a numeric string num and an integer target. We must insert binary operators, specifically '+', '-', and '*', between the digits of the string so that the resulting mathematical expression evaluates exactly to target.
The important detail is that we are not allowed to reorder digits. We may only decide:
- Where to split the string into operands
- Which operator to place between operands
For example, if num = "123", we can create expressions like:
"1+2+3""1*2*3""12-3""1+23"
But we cannot rearrange digits into something like "321".
The output should contain all valid expressions that evaluate to the target value.
Another critical rule is that operands cannot contain leading zeros. This means:
"0"is valid"5"is valid"10"is valid"05"is invalid"00"is invalid as a multi-digit operand
This restriction is one of the most common sources of bugs in this problem.
The constraints are relatively small:
num.length <= 10
At first glance, this may seem tiny, but the number of possible expressions grows exponentially because at every position we can:
- Continue building the current number
- Insert
+ - Insert
- - Insert
*
This immediately suggests a combinatorial search problem.
A naive implementation could generate every possible expression string and evaluate it afterward, but repeated parsing and evaluation would be extremely inefficient. A better approach is to build expressions incrementally while simultaneously tracking their evaluated value.
There are several important edge cases:
- Strings containing zeros, such as
"105"or"000" - Expressions requiring multiplication precedence
- Large intermediate values
- Cases where no valid expression exists
- Single-digit inputs
The multiplication precedence issue is especially important because expressions are evaluated according to normal arithmetic rules. For example:
1 + 2 * 3 = 7
not:
(1 + 2) * 3 = 9
Any correct solution must properly handle operator precedence during construction.
Approaches
Brute Force Approach
The brute force strategy is to generate every possible expression by trying all possible operator insertions between digits. Once an expression is generated, we evaluate it using a parser or built-in evaluation function.
For a string of length n, there are n - 1 gaps between digits. At each gap, we have several choices:
- Insert
+ - Insert
- - Insert
* - Insert nothing, meaning extend the current number
This creates an exponential number of possible expressions.
Although brute force guarantees correctness because it explores every possible expression, it is inefficient because:
- Every candidate expression must be constructed
- Every expression must then be parsed and evaluated
- Operator precedence must be handled separately
- Many invalid expressions with leading zeros may be generated
The repeated parsing cost makes this approach unnecessarily expensive.
Optimal Backtracking Approach
The key insight is that we can evaluate expressions incrementally while constructing them.
Instead of generating a full expression and evaluating later, we maintain:
- The current expression string
- The current evaluated value
- The last operand used
Tracking the last operand is the crucial trick that allows multiplication precedence to work correctly.
Suppose we currently have:
1 + 2
with value 3.
If we now append *3, the correct evaluation becomes:
1 + (2 * 3) = 7
We can compute this by:
current_value - last_operand + (last_operand * current_num)
which becomes:
3 - 2 + (2 * 3) = 7
This eliminates the need for a full expression parser.
The algorithm uses depth-first search with backtracking to explore all valid operator placements efficiently.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(4^n * n) | O(4^n * n) | Generates all expressions, then evaluates each separately |
| Optimal | O(4^n) | O(n) excluding output | Builds and evaluates expressions simultaneously using backtracking |
Algorithm Walkthrough
- Start a depth-first search from the beginning of the string.
At every recursive call, we decide what the next operand should be. Since operands may contain multiple digits, we try every possible substring starting at the current index. 2. Build the current operand digit by digit.
For example, from "123" at index 0, we may choose:
"1""12""123"
Each becomes a candidate operand. 3. Reject operands with leading zeros.
If a number starts with '0' and has more than one digit, we stop exploring that branch immediately.
For example:
"0"is allowed"05"is rejected
- Handle the first operand specially.
The first number in the expression cannot have a preceding operator.
So for the first recursive step:
- expression becomes
"1" - current value becomes
1 - last operand becomes
1
- For all later operands, try all three operators.
Suppose the current operand is current_num.
For addition:
new_value = current_value + current_num
The last operand becomes positive current_num.
6. For subtraction:
new_value = current_value - current_num
The last operand becomes negative current_num.
Storing it as negative is important because multiplication adjustments depend on the sign. 7. For multiplication, adjust for precedence.
Suppose we currently have:
expression = "1+2"
current_value = 3
last_operand = 2
Appending *3 should produce:
1 + (2 * 3)
We compute:
new_value = current_value - last_operand + (last_operand * current_num)
which becomes:
3 - 2 + 6 = 7
The new last operand becomes:
last_operand * current_num
- Continue recursively until all digits are consumed.
When we reach the end of the string:
- If the evaluated value equals
target, we add the expression to the answer. - Otherwise, we discard it.
Why it works
The algorithm works because every recursive branch represents one unique valid expression construction. At every step, we correctly maintain the evaluated value of the partially built expression. The last_operand mechanism guarantees multiplication precedence is handled exactly as standard arithmetic requires. Since every valid operator placement and operand partition is explored once, the algorithm finds all correct expressions without duplicates.
Python Solution
from typing import List
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
result = []
def backtrack(
index: int,
expression: str,
current_value: int,
last_operand: int
) -> None:
if index == len(num):
if current_value == target:
result.append(expression)
return
for end in range(index, len(num)):
# Prevent leading zeros
if end > index and num[index] == '0':
break
current_str = num[index:end + 1]
current_num = int(current_str)
# First number in expression
if index == 0:
backtrack(
end + 1,
current_str,
current_num,
current_num
)
else:
# Addition
backtrack(
end + 1,
expression + "+" + current_str,
current_value + current_num,
current_num
)
# Subtraction
backtrack(
end + 1,
expression + "-" + current_str,
current_value - current_num,
-current_num
)
# Multiplication
backtrack(
end + 1,
expression + "*" + current_str,
current_value - last_operand + (last_operand * current_num),
last_operand * current_num
)
backtrack(0, "", 0, 0)
return result
The implementation uses recursive backtracking to explore all possible expressions.
The backtrack function maintains four pieces of state:
index, the current position in the stringexpression, the expression constructed so farcurrent_value, the evaluated result of the expressionlast_operand, the most recent operand used
The loop generates all possible operands beginning at the current index.
The leading-zero check is extremely important:
if end > index and num[index] == '0':
break
This ensures values like "05" are never explored.
The first operand is handled separately because it cannot have a preceding operator.
For all later operands, the function recursively tries:
- Addition
- Subtraction
- Multiplication
Multiplication uses the precedence-adjustment formula:
current_value - last_operand + (last_operand * current_num)
This simulates proper arithmetic precedence without needing a parser or stack.
The recursion terminates when all digits are consumed. If the evaluated value equals the target, the expression is added to the result list.
Go Solution
package main
import (
"strconv"
)
func addOperators(num string, target int) []string {
var result []string
var backtrack func(
index int,
expression string,
currentValue int64,
lastOperand int64,
)
backtrack = func(
index int,
expression string,
currentValue int64,
lastOperand int64,
) {
if index == len(num) {
if currentValue == int64(target) {
result = append(result, expression)
}
return
}
for end := index; end < len(num); end++ {
// Prevent leading zeros
if end > index && num[index] == '0' {
break
}
currentStr := num[index : end+1]
currentNum, _ := strconv.ParseInt(currentStr, 10, 64)
// First operand
if index == 0 {
backtrack(
end+1,
currentStr,
currentNum,
currentNum,
)
} else {
// Addition
backtrack(
end+1,
expression+"+"+currentStr,
currentValue+currentNum,
currentNum,
)
// Subtraction
backtrack(
end+1,
expression+"-"+currentStr,
currentValue-currentNum,
-currentNum,
)
// Multiplication
backtrack(
end+1,
expression+"*"+currentStr,
currentValue-lastOperand+(lastOperand*currentNum),
lastOperand*currentNum,
)
}
}
}
backtrack(0, "", 0, 0)
return result
}
The Go implementation follows the same recursive strategy as the Python solution.
One notable difference is the use of int64 instead of int. Intermediate multiplication results can exceed normal 32-bit integer ranges, so using int64 avoids overflow issues.
Go slices are used to accumulate results dynamically. Unlike Python lists, Go slices require explicit append operations.
String concatenation is straightforward because the maximum input length is only 10, so performance remains acceptable without using a strings.Builder.
Worked Examples
Example 1
Input: num = "123", target = 6
We begin with index 0.
| Step | Expression | Current Value | Last Operand |
|---|---|---|---|
| Start | "" | 0 | 0 |
| Choose "1" | "1" | 1 | 1 |
Now from remaining "23":
| Step | Expression | Current Value | Last Operand |
|---|---|---|---|
| Add "2" | "1+2" | 3 | 2 |
| Multiply "3" | "1+2*3" | 7 | 6 |
This does not match target.
Another branch:
| Step | Expression | Current Value | Last Operand |
|---|---|---|---|
| "1*2" | 2 | 2 | |
| "1_2_3" | 6 | 6 |
Valid result found.
Another branch:
| Step | Expression | Current Value | Last Operand |
|---|---|---|---|
| "1+2" | 3 | 2 | |
| "1+2+3" | 6 | 3 |
Another valid result found.
Final output:
["1*2*3", "1+2+3"]
Example 2
Input: num = "232", target = 8
One successful branch:
| Step | Expression | Current Value | Last Operand |
|---|---|---|---|
| "2" | 2 | 2 | |
| "2+3" | 5 | 3 | |
| "2+3*2" | 8 | 6 |
Multiplication adjustment:
5 - 3 + (3 * 2) = 8
Another successful branch:
| Step | Expression | Current Value | Last Operand |
|---|---|---|---|
| "2*3" | 6 | 6 | |
| "2*3+2" | 8 | 2 |
Final output:
["2*3+2", "2+3*2"]
Example 3
Input: num = "3456237490", target = 9191
The algorithm exhaustively explores all valid expressions but none evaluate to 9191.
Final output:
[]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(4^n) | Each position can branch into multiple operator choices and substring splits |
| Space | O(n) | Recursion depth and expression construction require linear auxiliary space |
The algorithm explores an exponential search space because every gap between digits may either continue the current number or introduce one of three operators. Although the exact branching factor varies, the upper bound is exponential.
The recursion depth is at most n, where n is the length of the input string. Excluding the output list itself, auxiliary space usage remains linear.
Test Cases
from typing import List
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
result = []
def backtrack(index, expression, current_value, last_operand):
if index == len(num):
if current_value == target:
result.append(expression)
return
for end in range(index, len(num)):
if end > index and num[index] == '0':
break
current_str = num[index:end + 1]
current_num = int(current_str)
if index == 0:
backtrack(
end + 1,
current_str,
current_num,
current_num
)
else:
backtrack(
end + 1,
expression + "+" + current_str,
current_value + current_num,
current_num
)
backtrack(
end + 1,
expression + "-" + current_str,
current_value - current_num,
-current_num
)
backtrack(
end + 1,
expression + "*" + current_str,
current_value - last_operand + (last_operand * current_num),
last_operand * current_num
)
backtrack(0, "", 0, 0)
return result
sol = Solution()
# Basic examples
assert sorted(sol.addOperators("123", 6)) == sorted(["1+2+3", "1*2*3"]) # standard example
assert sorted(sol.addOperators("232", 8)) == sorted(["2*3+2", "2+3*2"]) # multiplication precedence
assert sol.addOperators("3456237490", 9191) == [] # no valid expressions
# Leading zero handling
assert sorted(sol.addOperators("105", 5)) == sorted(["1*0+5", "10-5"]) # prevent "05"
assert sorted(sol.addOperators("00", 0)) == sorted([
"0+0",
"0-0",
"0*0"
]) # multiple zero combinations
# Single digit
assert sol.addOperators("5", 5) == ["5"] # single exact match
assert sol.addOperators("5", 10) == [] # single non-match
# Larger concatenated operands
assert sorted(sol.addOperators("123", 123)) == ["123"] # no operators needed
# Negative results
assert sorted(sol.addOperators("123", -4)) == sorted(["1-2-3"]) # negative target
# Multiplication precedence
assert sorted(sol.addOperators("123", 7)) == sorted(["1+2*3"]) # precedence correctness
| Test | Why |
|---|---|
"123", 6 |
Validates standard branching |
"232", 8 |
Validates multiplication precedence |
"3456237490", 9191 |
Validates no-solution scenario |
"105", 5 |
Validates leading-zero prevention |
"00", 0 |
Validates multiple zero operands |
"5", 5 |
Validates single-digit success |
"5", 10 |
Validates single-digit failure |
"123", 123 |
Validates full-number operand |
"123", -4 |
Validates subtraction behavior |
"123", 7 |
Validates precedence adjustment |
Edge Cases
One critical edge case involves leading zeros. Inputs like "105" can easily produce invalid operands such as "05" if the algorithm is careless. Many naive solutions incorrectly allow these expressions. The implementation prevents this by stopping expansion immediately when a multi-digit operand begins with '0'.
Another important edge case is multiplication precedence. Expressions such as "1+2*3" must evaluate to 7, not 9. A naive left-to-right evaluation would produce incorrect results. The implementation solves this by tracking the previous operand separately and adjusting the running total during multiplication.
A third edge case is repeated zeros, such as "000". These inputs generate many valid expressions because each zero may participate independently in arithmetic operations. However, operands like "00" remain invalid. The recursive construction carefully allows single-digit zero operands while rejecting longer ones with leading zeros.
A fourth edge case is when the entire string itself forms the target. For example:
num = "123"
target = 123
The algorithm correctly handles this because one recursive branch chooses the entire remaining substring as a single operand without inserting operators.
Finally, large intermediate multiplication results can overflow smaller integer types in some languages. The Go solution uses int64 to safely accommodate intermediate computations during recursive evaluation.