282.md

282. Expression Add Operators

Solution 1 (time O(4^n), space O(n))

class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        ans = []
        n = len(num)

        def dfs(cur_expr, cur_ind, cur_target, cur_mul):
            if cur_ind == n:
                if cur_target == target:
                    ans.append("".join(cur_expr))
                return
            prev_len = len(cur_expr)
            if cur_ind > 0:
                cur_expr.append("")
            cur_val = 0
            for i in range(cur_ind, n):
                if i > cur_ind and num[cur_ind] == "0":
                    break
                cur_val = cur_val * 10 + int(num[i])
                cur_expr.append(num[i])
                if cur_ind == 0:
                    dfs(cur_expr, i + 1, cur_val, cur_val)
                else:
                    cur_expr[prev_len] = "+"
                    dfs(cur_expr, i + 1, cur_target + cur_val, cur_val)
                    cur_expr[prev_len] = "-"
                    dfs(cur_expr, i + 1, cur_target - cur_val, -cur_val)
                    cur_expr[prev_len] = "*"
                    dfs(cur_expr, i + 1, cur_target - cur_mul + cur_val * cur_mul, cur_val * cur_mul)
            del cur_expr[prev_len:]    
        
        dfs([], 0, 0, 0)
        return ans