282. Expression Add Operators

282

HardBacktrackingDFS building expressions while tracking the last operand for precedenceBacktracking over operator insertion with multiplication carry

Expression Add Operators

Given a string num of digits and an integer target, insert the binary operators +, -, and * (and choose multi-digit operands) between the digits so the resulting arithmetic expression evaluates to target. Return all such expressions. Operands may not have leading zeros.

Open official problem prompt ↗

In plain English

Produce every arithmetic string formed by grouping the digits into operands and inserting +, -, or * that evaluates to the target.

Picture it like this

Like filling the gaps between beads on a string with plus, minus, or times signs (or gluing beads into a bigger number), then checking if the whole thing computes to the target; multiplication is tricky because it reaches back and rewrites the previous addition.

Example

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Why: 1*2*3 = 6 and 1+2+3 = 6 are the only ways to insert operators between 1, 2, 3 to reach 6.

Constraints

1 <= num.length <= 10num consists of only digits-2^31 <= target <= 2^31 - 1Operands cannot contain leading zeros

Pattern lesson

See the pattern, then code

Backtracking over operator insertion with multiplication carry

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. Carry the running value and the last operand added; for multiplication, subtract the last operand and re-add last*current so precedence is handled without re-parsing.

New words, made simpleKnow these before the algorithm

Operand: A consecutive run of digits treated as one number, e.g. '12' in '1+23'.
last operand: The value most recently combined into the total, needed to correctly apply the next multiplication.
Precedence carry: The trick cur_val - last + last*val that removes the prior term and reinserts it multiplied.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Insert operators then eval() each string

Correct but re-parses precedence repeatedly and is slow and fragile.

Generate all operator placements and evaluate each expression with a parser.

Time O(4^n * n)Space O(n)

Best choiceBacktracking carrying value and last operand

Handles precedence incrementally and prunes leading zeros as operands are formed.

Track the running total and the last term so multiplication is applied in O(1) without re-parsing.

Time O(4^n)Space O(n)

The rule we keep true

Invariant

cur_val equals the value of the expression string built so far under normal precedence, and last equals the signed value of its final additive term.

Why this is correct

Reasoning

For + and - the new operand becomes a fresh additive term, so last is set to that signed value. For *, the previous term must bind tighter: removing last and adding last*val transforms a+b into a+(b*c), exactly matching operator precedence, so cur_val stays correct at every step.

The algorithm in three movesSay these aloud before coding

1Extend an operand num[index:end], breaking if it has a leading zero

expr='1', val=1, last=1

2At the first operand, seed the value and last with it (no operator)

'1*2': val = 1-1+1*2 = 2, last=2

3For +, add the operand and set last to +operand

'1*2*3': val = 2-2+2*3 = 6 -> record

4For -, subtract and set last to -operand

5For *, undo last then add last*operand, setting last to last*operand

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readindex=0, operand '1'

2 · AskFirst operand has no leading operator

3 · Update stateexpr='1', val=1, last=1

4 · ResultRecurse at index 1

Key takeaway

Digits 1, 2, 3 with operators being inserted in the gaps between them.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 7-10Terminal check
Once all digits are consumed, keep the expression only if it evaluates to target.
2
Lines 11-15Form the next operand
Extend the substring and break on a multi-digit operand starting with 0 to forbid leading zeros.
3
Lines 16-22Branch on operator
Seed at index 0, else recurse on +, -, and * with the precedence-carry formula for multiplication.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single digit equal to target returns [num]
Leading zero operands like '05' are forbidden but '0' alone is allowed
Intermediate values can exceed 32-bit range; Python big ints handle this naturally

Common beginner mistakes

Mishandling multiplication precedence by only tracking cur_val
Allowing '00' or '01' as operands
Forgetting that the first operand takes no leading operator
Using eval on untrusted-shaped strings instead of the O(1) carry

Check your understanding

Why is the multiplication update cur_val - last + last * val rather than cur_val * val?

PyPython 3 · solution.py

Optimal

1class Solution:2    def addOperators(self, num: str, target: int) -> list[str]:3        res: list[str] = []4        n = len(num)56        def backtrack(index: int, expr: str, cur_val: int, last: int) -> None:7            if index == n:8                if cur_val == target:9                    res.append(expr)10                return11            for end in range(index + 1, n + 1):12                s = num[index:end]13                if len(s) > 1 and s[0] == '0':14                    break15                val = int(s)16                if index == 0:17                    backtrack(end, s, val, val)18                else:19                    backtrack(end, expr + '+' + s, cur_val + val, val)20                    backtrack(end, expr + '-' + s, cur_val - val, -val)21                    backtrack(end, expr + '*' + s, cur_val - last + last * val, last * val)2223        backtrack(0, '', 0, 0)24        return res

Time complexityO(4^n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleMetaAirbnb

Expression Add Operators

Expression Add Operators

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking