# 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:

```python
+, -, *
```

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:

```python
"123"
```

can become:

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

but not:

```python
"3+2+1"
```

because digit order cannot change.

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

So:

```python
"0"
```

is valid, but:

```python
"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](https://leetcode.com/problems/expression-add-operators/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | String `num`, integer `target` |
| Output | List of valid expressions |
| Operators | `+`, `-`, `*` |
| Rule | Digit order cannot change |
| Rule | Multi-digit numbers cannot start with `0` |

Function shape:

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

## Examples

For:

```python
num = "123"
target = 6
```

Valid expressions are:

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

because:

```python
1 + 2 + 3 = 6
1 * 2 * 3 = 6
```

For:

```python
num = "232"
target = 8
```

Valid expressions are:

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

For:

```python
num = "105"
target = 5
```

Valid expressions are:

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

Notice:

```python
"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:

```python
+
-
*
nothing
```

For example:

```python
"123"
```

can produce:

```python
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:

```python
1 + 2 * 3
```

must evaluate to:

```python
7
```

not:

```python
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:

```python
current + value
current - value
```

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

Example:

```python
1 + 2 * 3
```

When we already have:

```python
1 + 2 = 3
```

and then see:

```python
*3
```

we cannot simply do:

```python
3 * 3
```

Instead:

```python
1 + (2 * 3)
```

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

We store:

| Variable | Meaning |
|---|---|
| `value` | Current evaluated result |
| `prev` | Last signed number added into the expression |

For multiplication:

```python
new_value = value - prev + (prev * current)
```

This correctly handles precedence.

## Algorithm

Use DFS with these parameters:

| Parameter | Meaning |
|---|---|
| `index` | Current position in `num` |
| `path` | Current expression string |
| `value` | Current evaluated value |
| `prev` | Last signed operand |

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:

```python
value - prev + prev * current
```

When we reach the end of the string:

```python
index == len(num)
```

check whether:

```python
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:

```python
value + current
```

correctly appends a positive term.

For subtraction:

```python
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:

```python
value = earlier + prev
```

When we append:

```python
* current
```

the multiplication must bind only to `prev`.

So the new value becomes:

```python
earlier + (prev * current)
```

which equals:

```python
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)`.

| Metric | Value | Why |
|---|---|---|
| Time | Exponential | We explore many partitions and operator combinations |
| Space | `O(n)` recursion depth | Maximum recursion depth equals string length |

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

This is expected for exhaustive backtracking problems.

## Implementation

```python
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:

```python
result = []
```

The DFS state contains:

```python
(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:

```python
if index == len(num):
```

we check whether the expression equals the target:

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

The loop chooses the next number substring:

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

This allows numbers like:

```python
1
12
123
```

We reject leading-zero numbers:

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

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

```python
if index == 0:
```

After the first number, we try all three operators.

Addition:

```python
value + current
```

Subtraction:

```python
value - current
```

Multiplication:

```python
value - prev + prev * current
```

This rewrites the last operand to respect multiplication precedence.

## Testing

```python
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:

| Test | Why |
|---|---|
| `"123", 6` | Basic addition and multiplication |
| `"232", 8` | Multiplication precedence |
| `"105", 5` | Leading-zero handling |
| `"00", 0` | Multiple valid zero expressions |
| `"3456237490", 9191` | No valid expression exists |