> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0282-expression-add-operators.md).

# 0282. Expression Add Operators

<https://leetcode.com/problems/expression-add-operators>

## Description

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

**Example 1:**

```
**Input:** num = "123", target = 6
**Output:** ["1*2*3","1+2+3"]
```

**Example 2:**

```
**Input:** num = "232", target = 8
**Output:** ["2*3+2","2+3*2"]
```

**Example 3:**

```
**Input:** num = "105", target = 5
**Output:** ["1*0+5","10-5"]
```

**Example 4:**

```
**Input:** num = "00", target = 0
**Output:** ["0*0","0+0","0-0"]
```

**Example 5:**

```
**Input:** num = "3456237490", target = 9191
**Output:** []
```

**Constraints:**

* `1 <= num.length <= 10`
* `num` consists of only digits.
* `-231 <= target <= 231 - 1`

## ac1: brute force DFS

```java
class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        // edge cases
        if (num == null || num.length() == 0) return res;

        dfs(num, 0, 0, 0, true, target, "", res);

        return res;        
    }
    private void dfs(String num, int start, long val1, long val2, boolean plus, int target, String note, List<String> res) {
        long value = plus ? val1 + val2 : val1 - val2;
        // exit
        if (start >= num.length()) {
            if (value == target) res.add(note);
            return;
        }

        for (int i = start + 1; i <= num.length(); i++) {
            if (num.charAt(start) == '0' && i > start + 1) break; // "05" is not allowed, 0 is fine

            long curr = Long.parseLong(num.substring(start, i));

            if (start == 0) { // start point
                dfs(num, i, value, curr, true, target, "" + curr, res);
            } else {
                dfs(num, i, value, curr, true, target, note + "+" + curr, res);
                dfs(num, i, value, curr, false, target, note + "-" + curr, res);
                dfs(num, i, val1, val2 * curr, plus, target, note + "*" + curr, res);
            }
        }
    }
}

/*
backtracking find all result
*/
```