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(“123”, 6)) == [“123″,”1+2+3″] assert sorted(Solution().addOperators(“232”, 8)) == [“23+2″,”2+32″] assert sorted(Solution().addOperators(“105”, 5)) == [“10+5″,”10-5″] assert sorted(Solution().addOperators(“00”, 0)) == [“00″,”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’]

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) {
            res.add(expr);
            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] == '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) 
                result.Add(path); 
            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 ); 
            } 
        } 
    } 
}