Expression Add Operators
Insert +, - and * between the digits of a string so the expression hits a target value. Backtracking where the hard part is handling multiplication precedence on the fly. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given a string num made only of digits, and an integer target. You may insert the binary operators +, - or * between any two adjacent digits, or insert nothing so the digits join into a longer number.
Return every expression you can build this way that evaluates to target under normal arithmetic precedence (* before + and -). The digits must stay in their original order and all of them must be used.
Numbers in the expression may not have leading zeros: "0" on its own is fine, but "05" is not. Return the expressions in any order.
Example 1
- Input
- num = "1234", target = 10
- Output
- ["1+2+3+4", "1*2*3+4"]
Example 2
- Input
- num = "105", target = 5
- Output
- ["1*0+5", "10-5"]
"1+05" is not allowed because 05 has a leading zero.
Example 3
- Input
- num = "999", target = 81
- Output
- []
No placement of operators reaches 81.
Constraints
- 1 ≤ num.length ≤ 10
- num contains only digits.
- -2³¹ ≤ target ≤ 2³¹ - 1
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Expression Add Operators in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Expression Add Operators
Pattern: Backtracking with a running value
At each gap between digits there are four choices (+, -, *, or join), so the search space is exponential no matter what. The goal is to make each step O(1) instead of re-evaluating the whole string at the end.
Addition and subtraction are easy to track: keep the running total. Multiplication is the catch, because it binds tighter than whatever came before. The fix is to also remember the last operand that was added (with its sign). When you multiply by x, undo that last operand and add last * x instead:
value = value - last + last * x, and the new last operand becomes last * x.
Leading zeros are handled by refusing to extend a number that starts with 0.
Approach 1: Generate every expression, then evaluate
Build all 4ⁿ⁻¹ strings and evaluate each with a small expression parser (or eval). Simple, but each evaluation costs O(n) and you still need to filter leading zeros afterwards.
Time O(n · 4ⁿ) · Space O(n)
Approach 2: Backtracking with value and last operand
Define dfs(i, path, value, last): digits before i are placed, value is what path evaluates to, and last is the last signed term.
- If
i == len(num), recordpathwhenvalue == target. - For each end
j ≥ i, takex = int(num[i..j]). Stop extending ifnum[i] == '0'andj > i. - At the first position, start with
x. Otherwise recurse three ways:+x(value + x, lastx),-x(value - x, last-x), and*x(value - last + last * x, lastlast * x).
The string building is the only O(n) part of each step.
Time O(n · 4ⁿ) in the worst case, far less work per node than re-parsing · Space O(n) recursion, plus the output
| Approach | Time | Space |
|---|---|---|
| Generate every expression, then evaluate | O(n · 4ⁿ) | O(n) |
| Backtracking with value and last operand | O(n · 4ⁿ) in the worst case, far less work per node than re-parsing | O(n) recursion, plus the output |
Solution code
Try the practice editor first. Both solutions pass every test above.
Expression Add Operators solution in Python
def add_operators(num: str, target: int) -> list[str]:
results = []
def dfs(i, path, value, last):
if i == len(num):
if value == target:
results.append(path)
return
for j in range(i, len(num)):
if j > i and num[i] == "0":
break # no leading zeros
part = num[i : j + 1]
x = int(part)
if i == 0:
dfs(j + 1, part, x, x)
else:
dfs(j + 1, path + "+" + part, value + x, x)
dfs(j + 1, path + "-" + part, value - x, -x)
dfs(j + 1, path + "*" + part, value - last + last * x, last * x)
dfs(0, "", 0, 0)
return resultsExpression Add Operators solution in JavaScript
function addOperators(num, target) {
const results = [];
const dfs = (i, path, value, last) => {
if (i === num.length) {
if (value === target) results.push(path);
return;
}
for (let j = i; j < num.length; j++) {
if (j > i && num[i] === '0') break; // no leading zeros
const part = num.slice(i, j + 1);
const x = Number(part);
if (i === 0) {
dfs(j + 1, part, x, x);
} else {
dfs(j + 1, path + '+' + part, value + x, x);
dfs(j + 1, path + '-' + part, value - x, -x);
dfs(j + 1, path + '*' + part, value - last + last * x, last * x);
}
}
};
dfs(0, '', 0, 0);
return results;
}Common mistakes
- Treating `*` like `+` and `-` by applying it to the whole running total, which ignores precedence.
- Allowing numbers with leading zeros such as "05", or the opposite mistake of rejecting a lone "0".
- Putting an operator before the very first number, producing strings like "+1+2".
- Integer overflow in languages with 32-bit ints. A 10-digit number like 9999999999 does not fit; use 64-bit values.
What interviewers look for
Start by stating the branching factor and admitting the output itself can be exponential, so no approach is polynomial. That frees you to focus on doing O(1) work per step.
Then explain the last operand trick with a tiny example: for 2+3*4, after 2+3 the value is 5 and last is 3; multiplying by 4 gives 5 - 3 + 12 = 14. Walking through one case like this is what convinces an interviewer the precedence handling is right. Mention leading zeros before you start coding, since it is the most common bug.
Follow-up questions
How would you add division?
Treat it like multiplication: `value - last + last / x` with the new last being `last / x`. You must skip x = 0 and agree on the rounding rule, and with integer division the result depends on truncation, so many people switch to exact fractions.
What if you only needed to know how many expressions hit the target?
The same backtracking works without building strings, which saves the O(n) copy per step. Memoizing on (index, value, last) can help when many paths reach the same state, though in practice the state space is still large.
What if parentheses were allowed too?
Then it becomes an interval problem: compute the set of values each substring can produce by splitting it at every operator position and combining the sets of the two halves, like "different ways to add parentheses". Memoize by substring.
Companies that ask Expression Add Operators
Expression Add Operators is tagged by 99 companies in our interview dataset. The score shows how often it comes up at each company.
- Gigamon100%
- Pandora100%
- Turnberry Solutions100%
- Citiustech100%
- Duckduckgo100%
- Thg100%
- Encora97%
- Seagate94%
- Latitude Ai92%
- Pinterest90.2%
- Zapposcom90%
- Arcutis Biotherapeutics89%
- 1password89%
- Marvell87%
- Biontech84%
- ASML83%
- Palantir80%
- Couchbase80%
- Clear80%
- Merck79%
- Pagerduty77%
- Glance77%
- Baxter International76%
- Disco75%
and 75 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required