## Similar Problems

Similar Problems not available

# Expression Add Operators - Leetcode Solution

LeetCode: Expression Add Operators Leetcode Solution

Difficulty: Hard

Topics: math string backtracking

Problem Statement: Given a string num that contains only digits and an integer target, return all possibilities to add the binary operators '+', '-', or '*' between the digits of num so that the resultant expression evaluates to the target value.

Example 1:

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to the target value 6.
Example 2:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to the target value 8.
Example 3:

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]
Explanation: Both "1*0+5" and "10-5" evaluate to the target value 5.
Note that "1-05" is not a valid expression because the 5 has a leading zero.
Example 4:

Input: num = "00", target = 0
Output: ["0*0","0+0","0-0"]
Explanation: "0*0", "0+0", and "0-0" all evaluate to 0.
Note that "00" is not a valid expression because the 0 has a leading zero.
Example 5:

Input: num = "3456237490", target = 9191 Output: []

Approach: The idea is to use a helper function that takes in current value of num that is being parsed (as a string), current index of that number, the sum so far, the last number that was used for addition/subtraction, and the current expression (as a string) so far.

We use backtracking, that is, we do the following:

- Create a variable curr_num from the current index to all possible offsets(considering end index is len(num)-1) and parse it to an integer. This curr_num is the new number that can be added as is or by using some operator.
- Before processing curr_num, check if the curr_num has leading zeros i.e. if curr_num is not just single digit and has a leading zero, it is a violotion of given constraint and hence ignore that particular option(set of digits).
- If current index (cur_idx) is 0, add the curr_num to expression string. We cannot add operator now since we have no numbers before curr_num. So, in this case, we make a recursive call to our function for the curr_num and at the same time, append the curr_num to the expression.
- If cur_idx is greater than 0, we now have some numbers before this location in the string. Now, we need to add operators(+,-,
*) before the number. a. To evaluate multiplication operator,*'. b. If we want to use addition or subtraction, we simply add '+' or '-' along with curr_num to the expression string and make a recursive call.

simply subtract the last number and multiply with current number. Add the last number and new num separated by ' - At each recursive call we check if sum so far reaches target and we append in our resulting list expressions that equal target sum.

Caveat:

- As we need to parse curr_num till some offset in num string, we can do a bit optimization by parsing all the remaining digits of num from that index into single integer using integer.parse.

Below is the implementation of the solution.

class Solution: def addOperators(self, num: str, target: int) -> List[str]: def helper(cur_num, cur_idx, sum_so_far, last_num_used, expr_so_far): if cur_idx == len(num): if sum_so_far == target: self.res.append(expr_so_far) return

```
for i in range(cur_idx, len(num)):
# parsing integer part
if i > cur_idx and num[cur_idx] == '0':
break
curr_num = int(num[cur_idx:i+1])
if cur_idx == 0:
helper(curr_num, i+1, curr_num, curr_num, str(curr_num))
else:
helper(curr_num, i+1, sum_so_far+curr_num, curr_num, expr_so_far+'+'+str(curr_num))
helper(-curr_num, i+1, sum_so_far-curr_num, -curr_num, expr_so_far+'-'+str(curr_num))
new_num = last_num_used*curr_num
helper(new_num, i+1, sum_so_far - last_num_used +new_num,
new_num, expr_so_far+'*'+str(curr_num))
self.res = []
helper(0, 0, 0, 0, '')
return self.res
```

Complexity Analysis: Time complexity: O(4^N) Since for each of the N-1 numbers, we can place an operator(+,-,or*) or not. Hence, it gives us 4 options at each step. Space complexity: O(N) The recursion stack can go N level at max.

Test Cases:

Now, let's test our solution using the test cases specified in the problem statement as well as some additional test cases:

assert sorted(Solution().addOperators("123", 6)) == ["1*2*3","1+2+3"]
assert sorted(Solution().addOperators("232", 8)) == ["2*3+2","2+3*2"]
assert sorted(Solution().addOperators("105", 5)) == ["1*0+5","10-5"]
assert sorted(Solution().addOperators("00", 0)) == ["0*0","0+0","0-0"]
assert sorted(Solution().addOperators("3456237490", 9191)) == []

assert sorted(Solution().addOperators("00", 1)) == [] # since we cannot have leading zero assert sorted(Solution().addOperators("0000", 0)) == [] # since we cannot have leading zero assert sorted(Solution().addOperators("1000000009", 9)) == ['1+0+0+0+0+0+0+0+0+9']

## Expression Add Operators Solution Code

`1`