# Solution For Expression Add Operators

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: [“123″,”1+2+3″] Explanation: Both “123″ and “1+2+3” evaluate to the target value 6.
Example 2:

Input: num = “232”, target = 8
Output: [“23+2″,”2+32″] Explanation: Both “23+2″ and “2+32″ evaluate to the target value 8.
Example 3:

Input: num = “105”, target = 5
Output: [“10+5″,”10-5″] Explanation: Both “10+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: [“00″,”0+0″,”0-0″] Explanation: “00″, “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:
1. 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.
2. 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).
3. 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.
4. 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,
simply subtract the last number and multiply with current number.
Add the last number and new num separated by ‘
‘.
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.
5. 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:
1. 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(“00”, 1)) == [] # since we cannot have leading zero
assert sorted(Solution().addOperators(“0000”, 0)) == [] # since we cannot have leading zero

## Step by Step Implementation For Expression Add Operators

```public class Solution {
public List addOperators(String num, int target) {
List res = new ArrayList<>();
if (num == null || num.length() == 0) return res;
dfs(num, target, 0, 0, "", res);
return res;
}

public void dfs(String num, int target, long currRes, long prevNum, String expr, List res) {
if (currRes == target && num.length() == 0) {
return;
}
for (int i = 1; i <= num.length(); i++) {
String currNum = num.substring(0, i);
if (currNum.length() > 1 && currNum.charAt(0) == '0') return;
String next = num.substring(i);
if (expr.length() > 0) {
dfs(next, target, currRes + Long.parseLong(currNum), Long.parseLong(currNum), expr + "+" + currNum, res);
dfs(next, target, currRes - Long.parseLong(currNum), -Long.parseLong(currNum), expr + "-" + currNum, res);
dfs(next, target, currRes - prevNum + prevNum * Long.parseLong(currNum), prevNum * Long.parseLong(currNum), expr + "*" + currNum, res);
} else {
dfs(next, target, Long.parseLong(currNum), Long.parseLong(currNum), currNum, res);
}
}
}
}```
```def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
res = []
self.helper(num, target, 0, 0, "", res)
return res

def helper(self, num, target, pos, eval, path, res):
if pos == len(num):
if eval == target:
res.append(path)
return

for i in range(pos, len(num)):
if i != pos and num[pos] == "0":
break
cur = num[pos:i + 1]
cur_val = int(cur)
if pos == 0:
self.helper(num, target, i + 1, cur_val, cur, res)
else:
self.helper(num, target, i + 1, eval + cur_val, path + "+" + cur, res)
self.helper(num, target, i + 1, eval - cur_val, path + "-" + cur, res)
self.helper(num, target, i + 1, eval - last_val + last_val * cur_val, path + "*" + cur, res)
last_val = cur_val```
```var addOperators = function(num, target) {
var result = [];

var dfs = function(num, target, temp, prev, i) {
if (i === num.length && target === 0) {
result.push(temp);
return;
}

for (var j = i; j < num.length; j++) {
if (num[i] === '0' && j !== i) break;

var curr = parseInt(num.substring(i, j + 1));

if (i === 0) {
dfs(num, target - curr, curr + '', curr, j + 1);
} else {
dfs(num, target + prev - curr, temp + '+' + curr, curr, j + 1);
dfs(num, target + prev + curr, temp + '-' + curr, -curr, j + 1);
dfs(num, target + prev * curr, temp + '*' + curr, prev * curr, j + 1);
}
}
};

dfs(num, target, '', 0, 0);

return result;
};```
```class Solution {
public:
vector addOperators(string num, int target) {
vector res;
if(num.size() == 0) return res;
helper(num, target, 0, 0, "", res);
return res;
}
void helper(string num, int target, long long diff, long long curNum, string out, vector& res) {
if(num.size() == 0 && curNum == target) {
res.push_back(out);
return;
}
for(int i = 1; i <= num.size(); ++i) {
string cur = num.substr(0, i);
if(cur.size() > 1 && cur == '0') return;
string next = num.substr(i);
if(out.size() > 0) {
helper(next, target, stoll(cur), curNum + stoll(cur), out + "+" + cur, res);
helper(next, target, -stoll(cur), curNum - stoll(cur), out + "-" + cur, res);
helper(next, target, diff * stoll(cur), (curNum - diff) + (diff * stoll(cur)), out + "*" + cur, res);
} else {
helper(next, target, stoll(cur), stoll(cur), cur, res);
}
}
}
};```
```public class Solution {
public IList AddOperators(string num, int target) {
IList result = new List();
if(num == null || num.Length == 0) return result;
DFS(result, "", num, target, 0, 0, 0);
return result;
}

public void DFS(IList result, string path, string num, int target, int position, long eval, long multed) {
if(position == num.Length) {
if(target == eval)
return;
}
for(int i = position; i < num.Length; i++) {
if(i != position && num[position] == '0') break;
long cur = Convert.ToInt64(num.Substring(position, i - position + 1));
if(position == 0) {
DFS(result, path + cur, num, target, i + 1, cur, cur);
} else {
DFS(result, path + "+" + cur, num, target, i + 1, eval + cur, cur);

DFS(result, path + "-" + cur, num, target, i + 1, eval - cur, -cur);

DFS(result, path + "*" + cur, num, target, i + 1, eval - multed + multed * cur, multed * cur );
}
}
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]