class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:

        #TC: O(N * 4^N)
        #SC: O(N)

        res = []

        def helper(index, accum, candi, prev):       
            if index == len(num):
                if accum == target:
                    res.append(candi[1:])          
                return

            for i in range(index, len(num)):

                val = int(num[index:i+1])

                helper(i+1, accum + val, candi + '+' + str(val), val)
                if index > 0:
                    helper(i+1, accum - val, candi + '-' + str(val), -val)
                    helper(i+1, accum - prev + prev*val, candi + '*' + str(val), prev*val)

                if int(num[index]) == 0:
                    break

        helper(0, 0, "", 0)
        return res