class Solution:
	def addOperators(self, num, target):
		if len(num) == 0: return []

		def helper(start):
			if start == len(nums):
				if data[0] + data[1] == target:
					ret.append("".join(cache))
				return

			operand = 0
			data0 = data[0]
			data1 = data[1]

			for i in range(start, len(nums)):
				operand = operand * 10 + nums[i]

				#add
				data[0] = data0 + data1
				data[1] = operand
				cache.append("+{:d}".format(operand))
				helper(i+1)
				cache.pop()

				data[0] = data0 + data1
				data[1] = -operand
				cache.append("-{:d}".format(operand))
				helper(i+1)
				cache.pop()

				data[0] = data0
				data[1] = data1 * operand
				cache.append("*{:d}".format(operand))
				helper(i+1)
				cache.pop()

				if operand == 0:
					break


		nums = [int(e) for e in num]
		data = [0, 1]
		cache = []
		ret = []

		operand = 0
		for i in range(len(nums)):
			operand = operand * 10 + nums[i]

			data[1] = operand
			cache.append(str(operand))
			helper(i+1)
			cache.pop()

			if operand == 0:
				break


		return ret



num = "105"
target = 5
print(Solution().addOperators(num, target))