# Iterative TLE - can improve?

• 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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.