Given a string S that contains only digits (0-9) and an integer target, return all possible strings to insert the binary operator ' + ', ' - ', or ' * ' between the digits of S so that the resultant expression evaluates to the target value.
Note:
 Operands in the returned expressions should not contain leading zeros. For example, 2 + 03 is not allowed whereas 20 + 3 is fine. It is allowed to not insert any of the operators.
If no solution is found, return an empty string array.
Example 1:
Input:
S = "123"
target = 6
Output: { "1*2*3", "1+2+3"}
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.
Example 2:
Input:
S = "3456237490"
target = 9191
Output: { } 
Explanation: There are no expressions that can be created from "3456237490"  to evaluate to 9191.
Example 3:
Input:
S = "12"
target = 12
Output: { "12"} 
Explanation: S itself matches the target. No other strings are possible.
Your Task:
You don't need to read input or print anything. Your task is to complete the function addOperators() which takes string S and integer target as parameters and returns a list of strings that contains all valid possibilities.
Expected Time Complexity: O(|S|*4^{|}^{S|})
Expected Auxiliary Space: O(|s|*3^{|S|})
Constraints:
1 ≤ |S| ≤ 10
S consists of only digits.
-2^{31 }≤ target ≤ 2^{31}-1

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(|S|*4^{|}^{S|})
Expected Auxiliary Space: O(|s|*3^{|S|})

Starter code:
#User function Template for python3



class Solution:

    def addOperators(self, S, target):

        # Code here

Solutions:
class Solution:

	def solve(self, ind, S, target, evalu, ans, res, mul):
		if ind == len(S):
			if evalu == target:
				res.append(ans)
			return
		for i in range(ind, len(S)):
			if ind != i and S[ind] == '0':
				break
			cur = int(S[ind:i + 1])
			if ind == 0:
				self.solve(i + 1, S, target, cur, ans + str(cur), res, cur)
			else:
				self.solve(i + 1, S, target, evalu + cur, ans + '+' + str(cur), res, cur)
				self.solve(i + 1, S, target, evalu - cur, ans + '-' + str(cur), res, -cur)
				self.solve(i + 1, S, target, evalu - mul + mul * cur, ans + '*' + str(cur), res, mul * cur)

	def addOperators(self, S, target):
		if int(S) == target:
			return [S]
		ans = ''
		res = []
		self.solve(0, S, target, 0, ans, res, 0)
		return res


class Solution:

	def addops(self, target, value, S, index, seq, lastnum, lastop):
		if index == len(S):
			if value == target:
				self.res.append(seq)
			return
		maxend = len(S)
		if S[index] == '0':
			maxend = index + 1
		for end in range(index + 1, maxend + 1):
			number = int(S[index:end])
			self.addops(target, value + number, S, end, seq + '+' + str(number), number, '+')
			self.addops(target, value - number, S, end, seq + '-' + str(number), number, '-')
			if lastop == '+':
				self.addops(target, value - lastnum + lastnum * number, S, end, seq + '*' + str(number), lastnum * number, '+')
			elif lastop == '-':
				self.addops(target, value + lastnum - lastnum * number, S, end, seq + '*' + str(number), lastnum * number, '-')
			else:
				self.addops(target, value * number, S, end, seq + '*' + str(number), number, '*')

	def addOperators(self, S, target):
		self.res = []
		for i in range(1, len(S) + 1):
			number = S[0:i]
			self.addops(target, int(number), S, i, number, number, None)
			if number == '0':
				break
		return self.res


class Solution:

	def addOperators(self, num, target):

		def backtrack(path, prev_operand, curr_operand, value, index):
			if index == len(num):
				if value == target and curr_operand == 0:
					res.append(''.join(path[1:]))
				return
			curr_operand = curr_operand * 10 + int(num[index])
			str_op = str(curr_operand)
			if curr_operand > 0:
				backtrack(path, prev_operand, curr_operand, value, index + 1)
			path.append('+')
			path.append(str_op)
			backtrack(path, curr_operand, 0, value + curr_operand, index + 1)
			path.pop()
			path.pop()
			if path:
				path.append('-')
				path.append(str_op)
				backtrack(path, -curr_operand, 0, value - curr_operand, index + 1)
				path.pop()
				path.pop()
				path.append('*')
				path.append(str_op)
				backtrack(path, prev_operand * curr_operand, 0, value - prev_operand + prev_operand * curr_operand, index + 1)
				path.pop()
				path.pop()
		res = []
		backtrack([], 0, 0, 0, 0)
		return res


class Solution:

	def addOperators(self, S, target):
		ans = []

		def dfs(ind, res, sol, prev):
			if ind >= len(S):
				if sol == target:
					ans.append(''.join(res))
				return
			for i in range(ind, len(S)):
				cur_str = S[ind:i + 1]
				num = int(cur_str)
				if not res:
					dfs(i + 1, [cur_str], num, num)
				else:
					dfs(i + 1, res + ['+'] + [cur_str], sol + num, num)
					dfs(i + 1, res + ['-'] + [cur_str], sol - num, -num)
					dfs(i + 1, res + ['*'] + [cur_str], sol - prev + num * prev, num * prev)
				if S[ind] == '0':
					break
		dfs(0, [], 0, 0)
		return ans


class Solution:

	def addOperators(self, S, target):
		ans = []

		def dfs(ind, cur_res, cur_sum, prev):
			if ind >= len(S):
				if cur_sum == target:
					ans.append(''.join(cur_res))
				return
			for i in range(ind, len(S)):
				cur_str = S[ind:i + 1]
				cur_num = int(cur_str)
				if not cur_res:
					dfs(i + 1, [cur_str], cur_num, cur_num)
				else:
					dfs(i + 1, cur_res + ['+'] + [cur_str], cur_sum + cur_num, cur_num)
					dfs(i + 1, cur_res + ['-'] + [cur_str], cur_sum - cur_num, -cur_num)
					dfs(i + 1, cur_res + ['*'] + [cur_str], cur_sum - prev + cur_num * prev, cur_num * prev)
				if S[ind] == '0':
					break
		dfs(0, [], 0, 0)
		return ans


class Solution:

	def addOperators(self, S, target):

		def dfs(l, r, expr, cur, last, res):
			if l == r:
				if cur == target:
					res.append(expr)
				return
			for i in range(l + 1, r + 1):
				if i == l + 1 or (i > l + 1 and S[l] != '0'):
					(s, x) = (S[l:i], int(S[l:i]))
					if last == None:
						dfs(i, r, s, x, x, res)
					else:
						dfs(i, r, expr + '+' + s, cur + x, x, res)
						dfs(i, r, expr + '-' + s, cur - x, -x, res)
						dfs(i, r, expr + '*' + s, cur - last + last * x, last * x, res)
		res = []
		dfs(0, len(S), '', 0, None, res)
		return res


class Solution:

	def addOperators(self, S, target):
		n = len(S)
		res = []

		def f(ind, curr, cur_sum, prev):
			if ind == n:
				if cur_sum == target:
					res.append(''.join(curr[:]))
				return
			for i in range(ind, n):
				cur_str = S[ind:i + 1]
				cur_num = int(cur_str)
				if not curr:
					f(i + 1, [cur_str], cur_num, cur_num)
				else:
					f(i + 1, curr + ['+'] + [cur_str], cur_sum + cur_num, cur_num)
					f(i + 1, curr + ['-'] + [cur_str], cur_sum - cur_num, -cur_num)
					f(i + 1, curr + ['*'] + [cur_str], cur_sum - prev + prev * cur_num, prev * cur_num)
				if S[ind] == '0':
					break
		f(0, [], 0, 0)
		return res


class Solution:

	def addOperators(self, S, target):
		res = []

		def helper(curr_idx, curr_res, curr_sum, prev):
			if curr_idx >= len(S):
				if curr_sum == target:
					res.append(''.join(curr_res))
				return
			for i in range(curr_idx, len(S)):
				curr_str = S[curr_idx:i + 1]
				curr_S = int(curr_str)
				if not curr_res:
					helper(i + 1, [curr_str], curr_S, curr_S)
				else:
					helper(i + 1, curr_res + ['+'] + [curr_str], curr_sum + curr_S, curr_S)
					helper(i + 1, curr_res + ['-'] + [curr_str], curr_sum - curr_S, -curr_S)
					helper(i + 1, curr_res + ['*'] + [curr_str], curr_sum - prev + curr_S * prev, curr_S * prev)
				if S[curr_idx] == '0':
					break
		helper(0, [], 0, 0)
		return res


class Solution:

	def generate(self, num, target, curr, res, build, prevNumber, currSum, n):
		if curr == len(num):
			if currSum == target:
				res.append(build)
			return
		for length in range(1, n - curr + 1):
			number = num[curr:curr + length]
			if number[0] == '0' and len(number) > 1:
				continue
			currNum = int(number)
			self.generate(num, target, curr + length, res, build + '+' + number, currNum, currSum + currNum, n)
			self.generate(num, target, curr + length, res, build + '-' + number, -currNum, currSum - currNum, n)
			self.generate(num, target, curr + length, res, build + '*' + number, currNum * prevNumber, currSum - prevNumber + currNum * prevNumber, n)

	def addOperators(self, num: str, target: int):
		res = []
		n = len(num)
		for length in range(1, n + 1):
			number = num[:length]
			if number[0] == '0' and len(number) > 1:
				continue
			currNum = int(number)
			self.generate(num, target, length, res, number, currNum, currNum, n)
		return res


def getExprUtil(res, curExp, _input, target, pos, curVal, last):
	if pos == len(_input):
		if curVal == target:
			res.append(curExp)
		return
	for i in range(pos, len(_input)):
		if i != pos and _input[pos] == '0':
			break
		part = _input[pos:i + 1].strip()
		cur = int(part)
		if pos == 0:
			getExprUtil(res, curExp + part, _input, target, i + 1, cur, cur)
		else:
			getExprUtil(res, curExp + '+' + part, _input, target, i + 1, curVal + cur, cur)
			getExprUtil(res, curExp + '-' + part, _input, target, i + 1, curVal - cur, -cur)
			getExprUtil(res, curExp + '*' + part, _input, target, i + 1, curVal - last + last * cur, last * cur)

class Solution:

	def addOperators(self, S, target):
		res = []
		getExprUtil(res, '', S, target, 0, 0, 0)
		return res


class Solution:

	def addOperators(self, S, target):
		results = []

		def dfs(index, expression, value, prev_operand, target):
			if index == len(S):
				if value == target:
					results.append(expression)
				return
			operand = 0
			for i in range(index, len(S)):
				operand = operand * 10 + int(S[i])
				if index == 0:
					dfs(i + 1, str(operand), operand, operand, target)
				else:
					dfs(i + 1, expression + '+' + str(operand), value + operand, operand, target)
					dfs(i + 1, expression + '-' + str(operand), value - operand, -operand, target)
					dfs(i + 1, expression + '*' + str(operand), value - prev_operand + prev_operand * operand, prev_operand * operand, target)
				if operand == 0:
					break
		dfs(0, '', 0, 0, target)
		return results


class Solution:

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

		def backtracking(idx=0, path='', value=0, prev=None):
			if idx == len(num) and value == target:
				rtn.append(path)
				return
			for i in range(idx + 1, len(num) + 1):
				tmp = int(num[idx:i])
				if prev is None:
					backtracking(i, num[idx:i], tmp, tmp)
				else:
					backtracking(i, path + '+' + num[idx:i], value + tmp, tmp)
					backtracking(i, path + '-' + num[idx:i], value - tmp, -tmp)
					backtracking(i, path + '*' + num[idx:i], value - prev + prev * tmp, prev * tmp)
				if num[idx] == '0':
					break
		rtn = []
		backtracking()
		return rtn


class Solution:

	def addOperators(self, S, target):
		res = []

		def helper(ind, tmp, curr_sum, prev):
			if ind == len(S):
				if curr_sum == target:
					res.append(''.join(tmp))
				return
			for i in range(ind, len(S)):
				curr_str = S[ind:i + 1]
				curr_nums = int(curr_str)
				if not tmp:
					helper(i + 1, [curr_str], curr_nums, curr_nums)
				else:
					helper(i + 1, tmp + ['+'] + [curr_str], curr_nums + curr_sum, curr_nums)
					helper(i + 1, tmp + ['-'] + [curr_str], curr_sum - curr_nums, -curr_nums)
					helper(i + 1, tmp + ['*'] + [curr_str], curr_sum - prev + curr_nums * prev, curr_nums * prev)
				if S[ind] == '0':
					break
		helper(0, [], 0, 0)
		return res


class Solution:

	def addOperators(self, S, target):

		def dfs(S: str, tmp: str, curr: int, prev: int) -> None:
			nonlocal target
			if not S:
				if curr == target:
					ans.append(tmp)
				return
			for i in range(len(S)):
				(pref, suff) = (S[i + 1:], S[:i + 1])
				if i == 0 or (i > 0 and S[0] != '0'):
					dfs(pref, tmp + '+' + suff, curr + int(suff), int(suff))
					dfs(pref, tmp + '-' + suff, curr - int(suff), -int(suff))
					dfs(pref, tmp + '*' + suff, curr - prev + prev * int(suff), prev * int(suff))
			return
		(ans, target) = ([], target)
		for i in range(len(S)):
			if i == 0 or (i > 0 and S[0] != '0'):
				dfs(S[i + 1:], S[:i + 1], int(S[:i + 1]), int(S[:i + 1]))
		return ans


class Solution:

	def solve(self, i, S, target, ans, lst=[]):
		if i >= len(S):
			a = lst
			i = 0
			stack = []
			while i < len(a) - 1:
				if a[i + 1] == '*':
					mul = 1
					while i < len(a) - 1 and a[i + 1] == '*':
						mul = mul * int(a[i])
						i += 2
					if i <= len(a) - 1:
						mul = mul * int(a[i])
					stack.append(mul)
					i += 1
				else:
					stack.append(a[i])
					i += 1
			a = int(stack[0])
			for i in range(2, len(stack), 2):
				if stack[i - 1] == '-':
					a -= int(stack[i])
				else:
					a += int(stack[i])
			if a == target:
				res = ''
				stack = lst[:len(lst) - 1]
				for i in stack:
					res += str(i)
				if res not in ans:
					ans.append(res)
			return
		for j in range(i, len(S)):
			if len(S[i:j + 1]) > 1 and S[i:j + 1][0] == '0':
				continue
			lst.append(S[i:j + 1])
			lst.append('+')
			self.solve(j + 1, S, target, ans, lst)
			lst.pop()
			lst.append('-')
			self.solve(j + 1, S, target, ans, lst)
			lst.pop()
			lst.append('*')
			self.solve(j + 1, S, target, ans, lst)
			lst.pop()
			lst.pop()

	def addOperators(self, num, target):
		L = len(num)
		ans = set()

		def backtrack(i, total, last, expr):
			if i == L:
				if total == target:
					ans.add(expr)
				return
			for j in range(i, L):
				n = int(num[i:j + 1])
				if i == 0:
					backtrack(j + 1, n, n, str(n))
				else:
					backtrack(j + 1, total + n, n, expr + '+' + str(n))
					backtrack(j + 1, total - n, -n, expr + '-' + str(n))
					backtrack(j + 1, total - last + last * n, last * n, expr + '*' + str(n))
				if n == 0:
					break
		backtrack(0, 0, 0, '')
		return list(ans)
		ans = []
		self.solve(0, S, target, ans)
		return ans