class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        res = []
        if not num or len(num) == 0:
            return res
        self.helper(res, '', num, target, 0, 0, 0)
        return res

    def helper(self, res, path, num, target, pos, eval, multed):
        if pos == len(num):
            if eval == target:
                res.append(path)
            return

        for i in range(pos, len(num)):
            if i != pos and num[pos] == '0':
                break

            cur = int(num[pos: i + 1])
            if pos == 0:
                self.helper(res, path + str(cur), num, target, i + 1, cur, cur)
            else:
                self.helper(res, path + '+' + str(cur), num,
                            target, i + 1, eval + cur, cur)
                self.helper(res, path + '-' + str(cur), num,
                            target, i + 1, eval - cur, -cur)
                self.helper(res, path + '*' + str(cur), num,
                            target, i + 1, eval - multed + (multed * cur), multed * cur)

3c2c7f86af70f640d7d7f6e1554865ee5f4c4191
<mask token>

class Solution(object):
    <mask token>
    <mask token>

class Solution(object):

    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        res = []
        if not num or len(num) == 0:
            return res
        self.helper(res, '', num, target, 0, 0, 0)
        return res
    <mask token>

class Solution(object):

    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        res = []
        if not num or len(num) == 0:
            return res
        self.helper(res, '', num, target, 0, 0, 0)
        return res

    def helper(self, res, path, num, target, pos, eval, multed):
        if pos == len(num):
            if eval == target:
                res.append(path)
            return
        for i in range(pos, len(num)):
            if i != pos and num[pos] == '0':
                break
            cur = int(num[pos:i + 1])
            if pos == 0:
                self.helper(res, path + str(cur), num, target, i + 1, cur, cur)
            else:
                self.helper(res, path + '+' + str(cur), num, target, i + 1,
                    eval + cur, cur)
                self.helper(res, path + '-' + str(cur), num, target, i + 1,
                    eval - cur, -cur)
                self.helper(res, path + '*' + str(cur), num, target, i + 1,
                    eval - multed + multed * cur, multed * cur)

class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        res = []
        if not num or len(num) == 0:
            return res
        self.helper(res, '', num, target, 0, 0, 0)
        return res

    def helper(self, res, path, num, target, pos, eval, multed):
        if pos == len(num):
            if eval == target:
                res.append(path)
            return

        for i in range(pos, len(num)):
            if i != pos and num[pos] == '0':
                break

            cur = int(num[pos: i + 1])
            if pos == 0:
                self.helper(res, path + str(cur), num, target, i + 1, cur, cur)
            else:
                self.helper(res, path + '+' + str(cur), num,
                            target, i + 1, eval + cur, cur)
                self.helper(res, path + '-' + str(cur), num,
                            target, i + 1, eval - cur, -cur)
                self.helper(res, path + '*' + str(cur), num,
                            target, i + 1, eval - multed + (multed * cur), multed * cur)
