282. Expression Add Operators (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        n = len(num)
        result = []
        def dfs(i, arr, s, res):
            if i == n:
                if res == target:
                    result.append(s[1 : ])
            else:
                if num[i] == "0":
                    dfs(i + 1, arr + [int(num[i])], s + "+" + num[i], res + int(num[i]))
                    dfs(i + 1, arr + [-int(num[i])], s + "-" + num[i], res - int(num[i]))
                    temp = arr[:]
                    m = temp.pop()
                    dfs(i + 1, temp + [0], s + "*0", res - m)
                else:
                    for j in range(i + 1, n + 1):
                        dfs(j, arr + [int(num[i : j])], s + "+" + num[i : j], res + int(num[i : j]))
                        dfs(j, arr + [-int(num[i : j])], s + "-" + num[i : j], res - int(num[i : j]))
                        temp = arr[:]
                        m = temp.pop()
                        dfs(j, temp + [m * int(num[i : j])], s + "*" + num[i : j], res - m + m * int(num[i : j]))
        if num[0] == "0":
            dfs(1, [0], "+0", 0)
        else:
            for i in range(n):
                dfs(i + 1, [int(num[ : i + 1])], "+" + num[ : i + 1], int(num[ : i + 1]))
        return result