**Solution**

**Expression Add Operators** https://leetcode.com/problems/expression-add-operators/

**Recursion and Backtracking**

- Make sure you understand the problem: 1234 does not mean adding brackets, we just need to add operators.
- 1234 = Processed "12" and now handle the substring "34".
- We could have processed "12" in many ways. But when we reach the part of "34", we just care about the value computed so far and the immediate prev value.
- For example: "1+2", "1-2", "1*2" would have a so_far value as 3,-1,2 and previous value as 2,-2,2.
- When we reach "34", we would have arrived from one of the paths like "1+2", "1-2", "1*2". We therefore know the prev value. This is needed for multiplication part since (1+2)*3 should be really 1+2*3 since we dont have any brackets. Hence we do 1+2-2+2*3

```
class Solution(object):
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
results = []
self.helper(0, num, 0, 0, "", target, results)
return results
def helper(self, k, num, ssum, prev, e, t, res):
if k == len(num):
if ssum == t:
res.append("".join([x for x in e]))
else:
for i in range(k, len(num)):
left = num[k:i+1]
ileft = int(left)
if left[0] == "0" and len(left) > 1: ### IGNORE INPUT LIKE "00", "005", "0006"
continue
if k == 0:
self.helper(i+1, num, ileft, ileft, left, t, res)
else:
self.helper(i+1, num, ssum+ileft, ileft, e+"+"+left, t, res)
self.helper(i+1, num, ssum-ileft, ileft*-1, e+"-"+left, t, res)
self.helper(i+1, num, ssum-prev+ileft*prev, ileft*prev, e+"*"+left, t, res)
return
```