> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/graph-search/bfsdfs/backtracking/expression-add-operators.md).

# 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);
            }
        }
    }
}
```