Given a string that contains only digits`0-9`

and a target value, return all possibilities to addbinaryoperators (not unary)`+`

,`-`

, or`*`

between the digits so they evaluate to the target value.

Initially, I adopted the strategy of using DFS to generate all possible strings containing digits and operators, and then evaluating each of them. However, this only made it super complicated. @czonzhu provides a clear and clean solution – we can do the generating strings and calculating values at the same time.

Here are several edge cases we need to deal with along with our DFS:

- At the beginning, we cannot put operators before the first digit.
- We cannot have numbers with leading zeros.
- When we put a
`*`

, we cannot multiply the coming number to the original value. Take`2+3*2`

as an example, when we process`2+3`

, we get`5`

. When we meet the`*`

, we cannot multiply`5`

with`2`

. The trick here is that we can remember the previous value`3`

.

#### Code

Comments are inserted to explaining how the edge cases get covered.

```
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
n,ret = len(num),[]
if n == 0: return []
def helper(ind,path,cnt,prev):
if ind == n:
if cnt == target: ret.append(path)
return
for i in range(ind,n):
# make sure do no generate numbers with leading zeros
if i != ind and num[ind] == '0': break
# cover cases when there is no operator between digits
cur = int(num[ind:i+1])
# do not put operators at the begining
if ind == 0:
helper(i+1,path+num[ind:i+1],cnt+cur,cur)
# record the previous value
else:
helper(i+1,path+'+'+num[ind:i+1],cnt+cur,cur)
helper(i+1,path+'-'+num[ind:i+1],cnt-cur,-cur)
helper(i+1,path+'*'+num[ind:i+1],cnt-prev+prev*cur,prev*cur)
helper(0,'',0,0)
return ret
```