Expression Add Operators
Asked at Pinterest
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.
Asked At
| 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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.