# 282. Expression Add Operators

Given a string that contains only digits`0-9`and a target value, return all possibilities to add **binary** operators (not unary)`+`,`-`, or`*`between the digits so they evaluate 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: []
```

**Thoughts:**

1. DFS: expanding each level:
   1. from curDepth to the end of the string, first extract the operand:
   2. if num\[curDepth] == '0', stop further expanding since we do not want a number with leading 0's
   3. if current level is 0, then expanding it as the first operator
   4. otherwise: expanding by appending the \['+', '-', '\*'] at the end

**Code**

```java
class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> ans = new ArrayList<>();
        if(num == null || num.length()== 0) return ans;
        dfs(ans, num, "", target, 0, 0, 0);
        return ans;
    }
    private void dfs(List<String> ans, String num,  String path, int target, int depth, long eval, long lastAdd){
        if(depth == num.length()){
            if(eval == target) ans.add(path);
            return;
        }

        for(int i = depth; i < num.length(); i++){
            // substring the operand, excluding the leading '0' ones 
            if(i > depth && num.charAt(depth) == '0') break;
            long cur = Long.parseLong(num.substring(depth, i + 1)); //[depth... i]
            // global first operand 
            if(depth == 0){
               dfs(ans, num , Long.toString(cur), target, i + 1, cur, cur); // leading element
            }
            else{
                //add
                dfs(ans,num,path + "+" + cur, target, i + 1, eval + cur, cur);
                //subtract
                dfs(ans,num,path + "-" + cur, target, i + 1, eval - cur, -cur);
                //multiply
                dfs(ans,num,path + "*" + cur, target, i + 1, eval - lastAdd + lastAdd * cur, lastAdd * cur);
            }
        }
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://code.taozirui.com/lc/graph-search/bfsdfs/backtracking/expression-add-operators.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.