class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        res=[]
        self.target=target
        for i in range(1,len(num)+1):
            if i==1 or (i>1 and num[0]!='0'):#to avoid '00'
                self.dfs(num[i:],num[:i],int(num[:i]),int(num[:i]),res)
        return res
        #last_val is the previous single value add to cur, in the case of adding '*' , last value need to be subtracted and added back after multiplication 
    def dfs(self,num,cur,cur_val,last_val,res):
        if not num: #if all the nums have been accounted for
            if cur_val==self.target:
                res.append(cur)
            else:
                return 
        else: 
            for i in range(1,len(num)+1):
                val=num[:i]
                
                if i==1 or (i>1 and num[0]!='0'): #to avoid '00'
                    self.dfs(num[i:],cur+'+'+val,cur_val+int(val),int(val),res)
                    self.dfs(num[i:],cur+'-'+val,cur_val-int(val),-int(val),res)
                    self.dfs(num[i:],cur+'*'+val,cur_val-last_val+last_val*int(val),last_val*int(val),res)