282 - Expression Add Operators
Written on October 28, 2015
Tweet
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value. reference
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
if not num:
return []
ret = []
self.helper(num, target, 0, 0, [], ret)
return ret
def helper(self, num, target, sums, prev, path, ret):
if len(num) == 0:
if sums == target:
ret.append("".join(path))
return
for i in range(1, len(num) + 1):
if num[0] == "0" and i > 1:
continue
n = int(num[:i])
if not path:
self.helper(num[i:], target, n, n, [str(n)], ret)
else:
self.helper(num[i:], target, sums + n, n, path + ["+", str(n)], ret)
self.helper(num[i:], target, sums - n, -n, path + ["-", str(n)], ret)
self.helper(num[i:], target, sums + prev * n - prev, prev * n, path + ["*", str(n)], ret)