282. Expression Add Operators
一道比较标准的backtracking的题目，不过中间的case有点多，没写出来
class Solution(object):
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
if not num: return []
paths = []
self.recur(paths,'',num,target,0,0,0)
return paths
def recur(self,paths,path,num,target,eva,pos,multed):
if pos == len(num) and eva == target:
paths.append(path)
return
for i in range(pos,len(num)):
if num[pos] == '0' and i > pos: break
cur = int(num[pos:i+1])
if pos == 0:
self.recur(paths,path+str(cur),num,target,eva+cur,i+1,eva+cur)
else:
self.recur(paths,path+'+'+str(cur),num,target,eva+cur,i+1,cur)
self.recur(paths,path+'-'+str(cur),num,target,eva-cur,i+1,-cur)
self.recur(paths,path+'*'+str(cur),num,target,eva+multed*(cur-1),i+1,multed*cur)
