282. Expression Add Operators
Asked at Pinterest
Difficulty
Hard
Time
O(n * 4^n)
Space
O(n)
Pattern
Math
Companies
1
Problem
You are given a string num that holds only digits, and an integer target. You must place the operators +, -, and * between some of the digits to build an expression. You may also leave digits joined together, so one operand can have many digits. Return all expressions that evaluate to target.
You do not have to use every operator, and you may use the same operator many times. The digits must stay in their original order — you only choose where to cut and which operator to insert.
One extra rule: an operand may not start with a zero unless the operand is exactly "0". So "05" is not allowed, but "0" alone is fine. Multiplication must follow normal math precedence, meaning * binds tighter than + and -.
Cut the digits and pick operators
Constraints
- ●
1 <= num.length <= 10 - ●
num consists of only digits. - ●
-2^31 <= target <= 2^31 - 1
Examples
num = "123", target = 6["1*2*3","1+2+3"]num = "232", target = 8["2*3+2","2+3*2"]num = "3456237490", target = 9191[]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Hard | View all Pinterest questions → |
How to Think About It
Generate all expressions and evaluate each one: 4^(n-1) expressions, each O(n) to evaluate. Too slow and awkward.
Key insight: evaluate as you build. Track the running value and the last operand that was added. For +x, value becomes value + x and last is x. For -x, value becomes value - x and last is -x.
Multiplication undoes the last operand and re-applies it multiplied: value - last + last * x, and the new last is last * x. This handles precedence — 2+3*4 becomes (2+3) - 3 + 3*4 = 14.
At each position, try every length for the next operand, num[pos..i]. Skip operands with a leading zero (like "05"), but a single "0" is fine.
Walkthrough for "232", target 8: 2*3+2 = 8 and 2+3*2 = 8. Result ["2*3+2","2+3*2"].
Optimal Approach
Step 1: dfs(pos, expr, value, last):
If pos == len(num): if value == target, record expr. Return.
For i from pos to end:
If i > pos and num[pos] == "0": break (leading zero).
cur = int(num[pos..i])
If pos == 0: dfs(i+1, str(cur), cur, cur).
Else:
dfs(i+1, expr + "+" + s, value + cur, cur)
dfs(i+1, expr + "-" + s, value - cur, -cur)
dfs(i+1, expr + "*" + s, value - last + last * cur, last * cur)
Step 2: Call dfs(0, "", 0, 0).
Time: O(n * 4^n) in the worst case. Space: O(n) recursion plus output.
Backtrack with running value and last operand
What Trips People Up in Real Interviews
Evaluating each full expression with a parser. You lose the pruning-free but linear-per-step evaluation that the last operand trick gives you.
Getting multiplication wrong. You must subtract the previous operand and add the product; simply multiplying the running value breaks precedence.
Allowing multi-digit operands with leading zeros like "05". Break out of the loop once the operand starts with 0 and has more than one digit.
Overflow in Java/C++. Operands of up to 10 digits exceed 32-bit ints — use long for value, last, and cur.
Putting an operator before the first operand. The first operand is placed without any sign.
Solution Code
O(n * 4^n) timedef addOperators(num, target):
res = []
def dfs(pos, expr, value, last):
if pos == len(num):
if value == target:
res.append(expr)
return
for i in range(pos, len(num)):
if i > pos and num[pos] == '0':
break
s = num[pos:i + 1]
cur = int(s)
if pos == 0:
dfs(i + 1, s, cur, cur)
else:
dfs(i + 1, expr + '+' + s, value + cur, cur)
dfs(i + 1, expr + '-' + s, value - cur, -cur)
dfs(i + 1, expr + '*' + s, value - last + last * cur, last * cur)
dfs(0, '', 0, 0)
return resFrequently Asked Questions
What is the Expression Add Operators problem?
Expression Add Operators gives you a string of digits and a target, and asks for every way to insert `+`, `-`, or `*` between digits so that the expression evaluates to the target. It is a backtracking problem whose real difficulty is handling multiplication precedence without re-evaluating the expression each time.
How do you solve Expression Add Operators?
The optimal approach runs in O(n * 4^n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Expression Add Operators?
Expression Add Operators is asked at Pinterest. It is a hard difficulty problem.
What are common mistakes on Expression Add Operators?
- Evaluating each full expression with a parser. You lose the pruning-free but linear-per-step evaluation that the `last` operand trick gives you.
- Getting multiplication wrong. You must subtract the previous operand and add the product; simply multiplying the running value breaks precedence.
- Allowing multi-digit operands with leading zeros like `"05"`. Break out of the loop once the operand starts with 0 and has more than one digit.
- Overflow in Java/C++. Operands of up to 10 digits exceed 32-bit ints — use `long` for `value`, `last`, and `cur`.
- Putting an operator before the first operand. The first operand is placed without any sign.