I'm wondering if it's possible to improve this approach or only a recursive DFS will work?

Between each digit of nums there are 4 possible operators: +, -, * and nothing.

I enumerate all expressions where each operator is inserted into each position. There are 4**(len(nums)-1) of these possible expressions.

Then each expression is evaluated to see if it is equal to target.

One extra check ensures I don't have a leading '0' for an integer apart from zero itself.

I think the advantage of dfs is that in reuses the evaluation of part of an expression, but here I create each full expression before evaluation it.

```
def addOperators(self, num, target):
if not num:
return [] if target else ['0']
expressions = []
mapping = {0 : '', 1 : '*', 2 : '+', 3 : '-'}
possibles = 4**(len(num)-1)
for possible in range(possibles):
expression = [num[0]]
for c in num[1:]:
possible, operator = divmod(possible, 4)
if operator == 0 and expression[-1] == '0' and len(expression) > 1 and not expression[-2].isdigit():
break
expression.append(mapping[operator])
expression.append(c)
else: # if no break, evaluate expression
expression = ''.join(expression)
if eval(expression) == target:
expressions.append(expression)
return expressions
```