LeetCode 282: Expression Add Operators

Problem Restatement

We are given:

• A string num containing only digits.
• An integer target.

We need to insert the operators:

+, -, *

between the digits so that the final mathematical expression evaluates exactly to target.

We must return all valid expressions.

Digits must remain in the original order.

We may also choose to join consecutive digits into a larger number.

For example:

"123"

can become:

"1+2+3"
"12-3"
"1*23"

but not:

"3+2+1"

because digit order cannot change.

Numbers with leading zeros are invalid except for the single digit "0".

So:

"0"

is valid, but:

"05"
"00"

are invalid multi-digit numbers.

The official statement asks us to return all expressions formed by inserting binary operators between digits so that the expression evaluates to target. The input size is small enough for exhaustive search with pruning. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def addOperators(self, num: str, target: int) -> list[str]:
        ...

Examples

For:

num = "123"
target = 6

Valid expressions are:

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

because:

1 + 2 + 3 = 6
1 * 2 * 3 = 6

For:

num = "232"
target = 8

Valid expressions are:

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

For:

num = "105"
target = 5

Valid expressions are:

[
    "1*0+5",
    "10-5"
]

Notice:

"1*05"

is invalid because "05" has a leading zero.

First Thought: Generate Everything

We could try every possible way to insert operators.

Between every pair of digits, we may choose:

+
-
*
nothing

For example:

"123"

can produce:

1+2+3
1-2+3
12+3
1*23
...

After generating each expression, we could evaluate it.

This works conceptually, but evaluating expressions correctly becomes difficult because multiplication has higher precedence.

For example:

1 + 2 * 3

must evaluate to:

7

not:

9

We need a cleaner way to track the value during construction.

Key Insight

We build the expression left to right using DFS.

At every step, we choose:

1. The next number segment.
2. Which operator to place before it.

The difficult part is multiplication.

For addition and subtraction, evaluation is easy:

current + value
current - value

But multiplication changes the previous term because multiplication has higher precedence.

Example:

1 + 2 * 3

When we already have:

1 + 2 = 3

and then see:

*3

we cannot simply do:

3 * 3

Instead:

1 + (2 * 3)

So we must remove the last added term and replace it with the multiplied value.

We store:

For multiplication:

new_value = value - prev + (prev * current)

This correctly handles precedence.

Algorithm

Use DFS with these parameters:

At each step:

1. Choose the next number substring.
2. Skip invalid leading-zero numbers.
3. If this is the first number, start the expression.
4. Otherwise try:
   • +
   • -
   • *

For multiplication:

value - prev + prev * current

When we reach the end of the string:

index == len(num)

check whether:

value == target

If yes, store the expression.

Correctness

The DFS explores every valid way to partition the digit string into numbers and insert operators between them.

At every recursive call, the expression represented by path evaluates exactly to value.

For addition:

value + current

correctly appends a positive term.

For subtraction:

value - current

correctly appends a negative term.

For multiplication, the previous operand prev has already been included in value.

Suppose the current expression evaluates as:

value = earlier + prev

When we append:

* current

the multiplication must bind only to prev.

So the new value becomes:

earlier + (prev * current)

which equals:

value - prev + (prev * current)

Therefore multiplication precedence is handled correctly.

The DFS tries all valid partitions and all valid operator choices, except numbers with illegal leading zeros. So every valid expression is generated exactly once.

When the recursion reaches the end of the digit string, the algorithm adds the expression only if its evaluated value equals target. Therefore every returned expression is correct.

Complexity

Let n = len(num).

The branching factor is high because each gap may contain multiple substring choices and multiple operators.

This is expected for exhaustive backtracking problems.

Implementation

class Solution:
    def addOperators(self, num: str, target: int) -> list[str]:
        result = []

        def dfs(index, path, value, prev):
            if index == len(num):
                if value == target:
                    result.append(path)
                return

            for end in range(index, len(num)):
                if end > index and num[index] == "0":
                    break

                current_str = num[index:end + 1]
                current = int(current_str)

                if index == 0:
                    dfs(
                        end + 1,
                        current_str,
                        current,
                        current
                    )
                else:
                    dfs(
                        end + 1,
                        path + "+" + current_str,
                        value + current,
                        current
                    )

                    dfs(
                        end + 1,
                        path + "-" + current_str,
                        value - current,
                        -current
                    )

                    dfs(
                        end + 1,
                        path + "*" + current_str,
                        value - prev + prev * current,
                        prev * current
                    )

        dfs(0, "", 0, 0)

        return result

Code Explanation

We store valid expressions here:

result = []

The DFS state contains:

(index, path, value, prev)

index tells where we are in the digit string.

path stores the current expression.

value stores the evaluated result.

prev stores the most recent signed operand.

When we reach the end:

if index == len(num):

we check whether the expression equals the target:

if value == target:
    result.append(path)

The loop chooses the next number substring:

for end in range(index, len(num)):

This allows numbers like:

1
12
123

We reject leading-zero numbers:

if end > index and num[index] == "0":
    break

The first number is special because it does not need an operator before it:

if index == 0:

After the first number, we try all three operators.

Addition:

value + current

Subtraction:

value - current

Multiplication:

value - prev + prev * current

This rewrites the last operand to respect multiplication precedence.

Testing

def test_add_operators():
    s = Solution()

    assert sorted(s.addOperators("123", 6)) == sorted([
        "1+2+3",
        "1*2*3"
    ])

    assert sorted(s.addOperators("232", 8)) == sorted([
        "2*3+2",
        "2+3*2"
    ])

    assert sorted(s.addOperators("105", 5)) == sorted([
        "1*0+5",
        "10-5"
    ])

    assert sorted(s.addOperators("00", 0)) == sorted([
        "0+0",
        "0-0",
        "0*0"
    ])

    assert s.addOperators("3456237490", 9191) == []

    print("all tests passed")

test_add_operators()

Test meaning: