Expression Add Operators

Explanation & Solution

Description

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Examples

Example 1

Input: num = "123", target = 6

Output:["1*2*3","1+2+3"]

1*2*3

1+2+3

Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2

Input: num = "232", target = 8

Output:["2*3+2","2+3*2"]

2*3+2

2+3*2

Explanation: "2*3+2" = 8 and "2+3*2" = 2+6 = 8.

Example 3

Input: num = "3456237490", target = 9191

Output: []

Explanation: No combination of operators produces 9191.

Constraints

1 <= num.length <= 10
num consists of only digits
-2³¹ <= target <= 2³¹ - 1

Approach

Backtracking pattern

1. Iterate Over Number Splits

At each position, try taking 1, 2, ... digits as the next operand
Skip multi-digit numbers with leading zeros (e.g., "05")

2. Handle the First Operand

The first number has no preceding operator — just set it as the starting expression and evaluation value

3. Try All Three Operators

For +: add the new value to the running total, track val as the previous operand
For -: subtract the value, track -val as the previous operand
For *: undo the last addition/subtraction (eval_ - prev), then apply prev * val — this correctly handles operator precedence

4. The Multiplication Trick

To handle * without building an expression tree, track the prev operand
For a + b * c: the running total is a + b, and prev = b. To apply * c, compute (a + b) - b + (b * c) = a + b*c

5. Collect Valid Expressions

When all digits are consumed (index === num.length), check if eval_ === target and add the expression to results

Key Insight

Tracking the prev operand is the critical insight — it allows correct multiplication precedence without an expression tree or stack. Each operator path carries enough state to evaluate correctly.

Time

O(4^n) where n is the length of num — at each digit we can split or continue, and choose from 3 operators

Space

O(n) for the recursion stack

Visualization

Input:

Backtracking Exploration

current path

empty

Press play to start

ExploringFoundBacktrack

23 steps

Solution Code

Word Search II

Combination Sum II