- "try everything" -> backtracking
- 4 branches at each level for each operation
- multiplication case needs to track the prev result and undo it due to order of operations
- leading 0 edge case
10 + 2 * 4 = (10 + 2) * 4 = 48 (wrong)
10 + 2 * 4 = (10 + 2 - +2) + (2 * 4) = 18 (right)
- make sure to exclude leading 0s
valid answers:
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
but with leading zeros we will have:
"105", 5 -> ["1*0+5","10-5", "1*05"]
"00", 0 -> ["0+0", "0-0", "0*0", "00"]
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
n = len(num)
def branch(path, l, soFar, prev_op):
if l == n:
if soFar == target:
res.append(path)
else:
for r in range(l, n): # don't restart from 0, start from the progressed idx
cur = num[l:r+1] # check 2 digit numbers e.g. '1'->'2' and '12'
if num[l] == '0' and len(cur) >= 2: break # exclude paths with leading 0 e.g. '+05'
op = int(cur)
if l == 0: # first number just put it down
branch(f'{cur}', r+1, op, op)
else:
branch(f'{path}+{cur}', r+1, soFar+op, +op)
branch(f'{path}-{cur}', r+1, soFar-op, -op)
branch(f'{path}*{cur}', r+1, (soFar-prev_op)+(prev_op*op), +(prev_op*op))
res = []
branch('', 0, 0, 0)
return res
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
def helper(path, l, soFar, prev_op):
if l == len(num):
if soFar == target:
res.append(path)
else:
for r in range(l, len(num)): # don't restart from 0, start from the progressed idx
cur = num[l:r+1] # check 2 digit numbers e.g. '1' vs. '10'
if num[l] == '0' and len(cur) >= 2: break # exclude paths with leading 0 e.g. '+05'
if l == 0: # first number just put it down
op = int(cur) ; helper(f'{cur}', r+1, op, op)
else:
op = +int(cur) ; helper(f'{path}+{cur}', r+1, soFar + op, op) # +
op = -int(cur) ; helper(f'{path}-{cur}', r+1, soFar + op, op) # -
op = int(prev_op) * int(cur) ; helper(f'{path}*{cur}', r+1, (soFar - prev_op) + op, op) # *
res = []
helper('', 0, 0, 0)
return res