[LeetCode] 282. Expression Add Operators

 Problem : https://leetcode.com/problems/expression-add-operators/

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        result = []
        
        def helper(num, diff, curNum, partial):
            if len(num) == 0 and curNum == target:
                result.append(partial)
                return
            
            for i in range(1, len(num)+1):
                cur = num[:i]
                
                
                if len(cur) > 1 and cur[0] == '0':
                    return
              
                if len(partial) == 0:
                    helper(num = num[i:], diff = int(cur), curNum = int(cur), partial = cur)
                else:
                    # A + B
                    helper(num = num[i:], diff = int(cur), curNum = curNum + int(cur), partial = partial + '+' + cur)
                
                    # A - B
                    helper(num = num[i:], diff = -1 * int(cur), curNum = curNum - int(cur), partial = partial + '-' + cur)
        
                    # A * B
                    helper(num = num[i:], diff = diff * int(cur), curNum = curNum - diff + diff * int(cur), partial = partial + '*' + cur)
                
        helper(num, 0, 0, "")
        
        return result

Instead of saving the diff of previous calculation, we may postpone the process of '+' operator.  The '-' operator can be considered as add a negative number.

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]: 
        result = []
        
        def backtrack(start, preNum, curNum, expr):
            """
            calculate preNum + curNum [operator] tmp
            [operator] = +, -, *
            """
            if start == len(num):
                if preNum + curNum == target:
                    result.append(expr)
                return
            
            tmp = 0
            for i in range(start, len(num)):
                tmp = tmp * 10 + int(num[i])
                
                # *  multiplication is the highest priority operator, we get the result of curNum * tmp right away.
                backtrack(i+1, preNum, curNum * tmp, expr + '*' + num[start:i+1])
                
                # +  addition is a low priority operator, save current partial result and postpone the calculation of + tmp
                backtrack(i+1, curNum + preNum, tmp, expr + '+' + num[start:i+1])
                
                # -  substruction is a low priority operator, save current partial result and postpone the calculation of + (-tmp)
                backtrack(i+1, curNum + preNum, -tmp, expr + '-' + num[start:i+1])
                
                if num[start] == '0':
                	# break to avoid number with leading '0'
                    break
            
        
        tmp = 0
        for i in range(len(num)):
            tmp = tmp * 10 + int(num[i])
            backtrack(i+1, 0, tmp, num[:i+1])
            if num[0] == '0':
                # break to avoid number with leading '0'
                break
        
        return result

Edited on 03/16/2021. An optimized version.

Edited on 09/18/20201. Add more comment to the 2nd solution which postpone the process of '+' operator.