Expression Add Operators
Problem Statement
Given a string num that contains only digits and an integer target, return all strings that can be formed by inserting addition, subtraction, or multiplication operators between some digits so the expression evaluates to target. You may also choose not to insert an operator between adjacent digits, which extends the current number. Operands cannot have leading zeroes unless the operand is exactly 0.
Input
A digit string num and an integer target.
Output
A list of valid expression strings whose evaluated value equals target.
Constraints
- •
1 <= num.length <= 10 - •
num consists only of digits - •
-2^31 <= target <= 2^31 - 1 - •
The answer expressions may be returned in any order
Examples
Example 1
num = 123, target = 6
[1+2+3, 1*2*3]Example 2
num = 232, target = 8
[2*3+2, 2+3*2]Example 3
num = 105, target = 5
[1*0+5, 10-5]Learning Objectives
- Recognise expression generation as a wide ordered decision tree over digit gaps.
- Track the evaluated prefix without reparsing the whole expression at every leaf.
- Use the previous operand to repair multiplication precedence after a prior addition or subtraction.
- Prune invalid operands with leading zeroes and compute with **long** values to avoid intermediate overflow.
Intuition
Pattern Recognition + Intuition
This is backtracking because every gap between digits asks the same question: insert addition, subtraction, multiplication, or insert nothing and keep growing the current operand. The choices are ordered and every final expression must preserve the original digit order, so a recursion tree naturally enumerates all candidates. Naive search explodes because each gap can branch several ways, and then each leaf would need expression evaluation.
The interview trick is to evaluate as you build. Addition and subtraction are easy: append the operand to the running value. Multiplication is harder because it has higher precedence than the operator that came before it. Carry previousOperand, the signed operand that was most recently added into value. When choosing multiplication by current, replace that previous contribution with the product: value - previousOperand + previousOperand * current. For 1+2*3, the prefix 1+2 has value = 3 and previousOperand = 2. Multiplying by 3 changes the value to 3 - 2 + 2 * 3 = 7, which matches normal precedence without reparsing the expression.
Common mistakes
- ×Evaluating the expression left to right and getting multiplication precedence wrong.
- ×Forgetting that **previousOperand** must be signed, so a subtraction stores the operand as negative.
- ×Allowing operands like **05**, which creates duplicate and invalid interpretations.
- ×Using **int** for intermediate values even though multiplication can exceed the target range during search.
Algorithm Explanation
State
Each recursion frame carries index, the next digit to consume; expression, the characters chosen so far; value, the evaluated value of the expression prefix; and previousOperand, the signed final operand currently included in value. From index, choose a substring num[index...end] as the next operand, unless it has a leading zero.
Recursion tree
For num = 123, the first level chooses 1, 12, or 123 as the first operand. From 1, the next operand can be 2 or 23. If it chooses 2, the operator branches create 1+2, 1-2, and 1*2. From 1+2, choosing 3 makes 1+2+3, 1+2-3, and 1+2*3. The multiplication branch does not use the visible left-to-right value 3 then multiply by 3; it rewrites the last contribution so the value becomes 1 + 2 * 3. For num = 105, after choosing 1, the substring 05 is pruned because an operand cannot start with zero.
Pruning
Skip any candidate number whose first digit is 0 and whose length is greater than one. Use long for value, previousOperand, and current so multiplication does not overflow ordinary integer arithmetic. Stop only at leaves: a candidate is valid when all digits are consumed and value == target. Non-leaf prefixes are not rejected merely because they are far from the target, since later subtraction or multiplication can change the value sharply.
Algorithm
- Start DFS at index = 0 with an empty expression, value = 0, and previousOperand = 0.
- At each frame, extend end from index to the end of the string to choose the next operand substring.
- Break the operand loop if the substring would have a leading zero.
- If this is the first operand, append it without an operator and recurse.
- Otherwise choose addition, recurse with value + current and previousOperand = current, then undo the expression.
- Choose subtraction, recurse with value - current and previousOperand = -current, then undo.
- Choose multiplication, recurse with value - previousOperand + previousOperand * current and previousOperand * current, then undo.
- When index reaches the end, add the expression only if the evaluated value equals target.
Solutions
Solution: DFS with previous operand rollback
Build the expression left to right and carry enough evaluation state to avoid reparsing it. The running value represents the expression after applying normal precedence for the prefix. The signed previousOperand is the last additive contribution. Multiplication removes that contribution and replaces it with the product, which handles precedence in constant time per choice.
Step-by-step
- Use a StringBuilder so each branch can append an operator and operand, recurse, then restore the previous length.
- Loop over every possible next operand substring starting at the current index.
- Stop the loop when a multi-digit operand would start with 0.
- For the first operand, append only the number and seed both value and previousOperand.
- For later operands, try addition, subtraction, and multiplication with the correct value updates.
- At the end of the digit string, record the expression if the accumulated value equals the target.
O(4^n * n)
O(n)
There are roughly four decisions per gap when counting concatenation and the three operators. Copying a successful expression costs up to n characters, while recursion depth and the builder length are linear.
Java implementation
Dry Run
Sample input
num = 105, target = 5. Track the running value and signed previous operand while important branches are explored.
| step | index | choice | expression | value | previous operand | result |
|---|---|---|---|---|---|---|
| 1 | 0 | start with 1 | 1 | 1 | 1 | continue |
| 2 | 1 | operator + and number 0 | 1+0 | 1 | 0 | continue |
| 3 | 2 | operator + and number 5 | 1+0+5 | 6 | 5 | leaf fails target 5 |
| 4 | 2 | operator * and number 5 | 1+0*5 | 1 | 0 | leaf fails target 5 |
| 5 | 1 | operator * and number 0 | 1*0 | 0 | 0 | continue |
| 6 | 2 | operator + and number 5 | 1*0+5 | 5 | 5 | leaf succeeds |
| 7 | 0 | start with 10 | 10 | 10 | 10 | continue |
| 8 | 2 | operator - and number 5 | 10-5 | 5 | -5 | leaf succeeds |
| 9 | 1 | try number 05 | blocked | n/a | n/a | leading zero prune |
The valid expressions are 1*0+5 and 10-5. The branch containing 05 is never explored, and multiplication uses the previous-operand rollback rather than a separate evaluator.
Interview Tips
Spend most of your explanation on multiplication. Say that value already includes the last operand, so multiplication must remove it and add the product. Also make the leading-zero rule explicit before coding; it is the most common source of extra invalid answers. Avoid target-based pruning unless you can prove it, because subtraction and multiplication can reverse apparent progress.
Likely follow-ups
- How would you add division while preserving integer truncation rules?
- How would you return only the count of expressions instead of the expressions themselves?
- How would you support parentheses as another choice in the expression tree?
- How would you avoid storing all answers if the output could be extremely large?
Similar Problems
Key Takeaways
- Expression generation is an ordered gap-decision tree over digits.
- Carry **value** and signed **previousOperand** to handle multiplication precedence online.
- Leading-zero operands are invalid except for the single digit **0**.
- Use **long** for intermediate arithmetic even when the target is an integer.