Problem Explanation

The problem asks to find all possible ways to insert binary operators (+, -, *) between the digits in a string so that the expression evaluates to the target value. If no possible expression can evaluate to the target value, return an empty list.

Walkthrough

Let's consider an example where the input string of digits ("num") is "123" and the target value is 6. As per the problem, we need to find all possible combinations to insert binary operators such that the resulting expression evaluates to 6.

One way to achieve this is as follows: "123". The multiplication of these 3 numbers results in 6. Setting them as the operands of a + operator will also give 6, such that "1+2+3". Therefore, the output for this example should be ["1+2+3", "123"].

Let's understand the approach of the Python solution provided above.

Solution Approach

We would use Depth-First Search (DFS) for this problem. We would generate all possible expressions by placing binary operators in between the digits, and then evaluate those expressions to check if they result in the target value.

We would recursively consider every possible case of adding one of the +, -, or * operators between each of the digits in the string. As we traverse the string, we keep track of the accumulated value (eval). For multiplication, we also need to keep track of the previously multiplied value (prev) to handle the order of operations (since multiplication has a higher precedence than addition/subtraction).

An important edge case is to handle leading zeroes - if a number has leading zeroes (after the first digit), we should ignore this number, as it wouldn't lead to a valid expression.

In the primary function addOperators, we are initiating the recursive dfs call and returning the resulted possible expressions.

Python Solution

1
2Python
3class Solution:
4    def addOperators(self, num: str, target: int) -> List[str]:
5        res = []
6        self.dfs(num, target, "", 0, 0, res)
7        return res
8        
9    def dfs(self, num, target, path, currSum, prevVal, res):
10        if not num:
11            if currSum == target:
12                res.append(path)
13            return 
14        for i in range(1, len(num)+1):
15            temp = num[:i]
16            nextNum = num[i:]
17            if i == 1 or (i > 1 and num[0] != "0"): # prevent the number having leading zero
18                if not path:
19                    self.dfs(nextNum, target, temp, int(temp), int(temp), res)
20                else:
21                    self.dfs(nextNum, target, path + "+" + temp, currSum + int(temp), int(temp), res)
22                    self.dfs(nextNum, target, path + "-" + temp, currSum - int(temp), -int(temp), res)
23                    self.dfs(nextNum, target, path + "*" + temp, currSum - prevVal + prevVal * int(temp), prevVal * int(temp), res)

Java Solution

1
2Java
3public class Solution {
4    public List<String> addOperators(String num, int target) {
5        List<String> ans = new ArrayList<>();
6        if (num.length() == 0) {
7            return ans;
8        }
9        dfs(ans, "", num, target, 0, 0);
10        return ans;
11    }
12
13    public void dfs(List<String> ans, String path, String num, int target, long eval, long multed) {
14        if (num.length() == 0 && target == eval) {
15            ans.add(path);
16            return;
17        }
18        for (int i = 1; i <= num.length(); i++) {
19            if (i != 1 && num.charAt(0) == '0') break;
20            long cur = Long.parseLong(num.substring(0, i));
21            String next = num.substring(i);
22            if (path.length() != 0) {
23                dfs(ans, path + "*" + cur, next, target, eval - multed + multed * cur, multed * cur);
24                dfs(ans, path + "+" + cur, next, target, eval + cur, cur);
25                dfs(ans, path + "-" + cur, next, target, eval - cur, -cur);
26            } else {
27                dfs(ans, path + cur, next, target, eval + cur, cur);    
28            }
29        }
30    }
31}

JavaScript Solution

1
2JavaScript
3var addOperators = function(num, target) {
4    let res = []
5    dfs(res, "", num, target, 0, 0)
6    return res
7};
8
9function dfs(ans, path, num, target, eval, multed) {
10    if (num.length === 0 && target === eval) {
11        ans.push(path)
12        return;
13    }
14    for (let i = 1; i <= num.length; i++) {
15        if (i !== 1 && num.charAt(0) === '0') break;
16        let cur = parseInt(num.substring(0, i))
17        let next = num.substring(i)
18        if (path.length !== 0) {
19            dfs(ans, path + "*" + cur, next, target, eval - multed + multed * cur, multed * cur)
20            dfs(ans, path + "+" + cur, next, target, eval + cur, cur)
21            dfs(ans, path + "-" + cur, next, target, eval - cur, -cur)
22        } else {
23            dfs(ans, path + cur, next, target, eval + cur, cur)
24        }
25    }
26}

C++ Solution

1
2cpp
3class Solution {
4    vector<string> ans;
5public:
6    vector<string> addOperators(string num, int target) {
7        if(num.size()==0) return {};
8        dfs(num, target, 0, 0, 0, "");
9        return ans;
10    }
11    
12    void dfs(string &num, int target, int idx, long prev, long mult, string path) {
13        if(idx==num.size() && target==prev) {
14            ans.push_back(path); 
15        }
16        for(int i=1; i<=num.size()-idx; ++i) {
17            string next=num.substr(idx, i);
18            if(next.size()>1 && next[0]=='0') return;
19            string curr=path+(idx==0?"":"+")+next;
20            dfs(num, target, idx+i, stol(next)+prev, stol(next), curr);
21            if(idx>0) {
22                dfs(num, target, idx+i, prev-stol(next), -stol(next), path+"-"+next);
23                dfs(num, target, idx+i, prev-mult+mult*stol(next), mult*stol(next), path+"*"+next);
24            }
25        }
26    } 
27};

C# Solution

1
2csharp
3public class Solution {
4    public IList<string> AddOperators(string num, int target) {
5        var result = new List<string>();
6        AddOperatorsDFS(num, target, 0, 0, 0, "", result);
7        return result;
8    }
9    
10    private void AddOperatorsDFS(string s, int target, int idx, long prevNum, long currNum, string path, IList<string> result) {
11        if(idx == s.Length && currNum == target) {
12            result.Add(path);
13            return;
14        }
15        for(int i = idx; i < s.Length; i++) {
16            if(s[idx] == '0' && i != idx)
17                break;
18            long num = long.Parse(s.Substring(idx, i+1-idx));
19            if(idx == 0) {
20                AddOperatorsDFS(s, target, i+1, num, num, path + num.ToString(), result);
21            }
22            else {
23                AddOperatorsDFS(s, target, i+1 , num, currNum + num, path + "+" + num.ToString(), result);
24                AddOperatorsDFS(s, target, i+1 , -num, currNum - num, path + "-" + num.ToString(), result);
25                AddOperatorsDFS(s, target, i+1 , prevNum * num, currNum - prevNum + prevNum * num, path + "*" + num.ToString(), result);
26            }
27        }
28    }
29}

Edge Cases

1. Empty "num": If "num" is an empty string, return empty list. e.g. num = "", target = 6, return [].
2. Negative target: Operators can give a negative result. e.g. num = "22", target = -2, return ["2-2*2"].
3. Non-exist solution: If no combination can evaluate to target, return empty list. e.g. num = "22", target = 10, return [].

Code Explanation

Python

We start by checking if "num" is empty. If it is, and if currSum equals target, we record this path into our result "res".

For distinguishing different "num", we need a for loop ranging from 1 to the length of "num" + 1. We then need to prevent the number having leading zero unless this number is zero itself. After passing the checks, we pass the path (if path isn't empty, append the operator and the "num") to the next level of decision tree. The trickiest part comes when considering the multiplication case. The currSum and prevVal for "+" are currSum + int(temp) and int(temp) respectfully. "-" also behaves similarly as "+". For multiplier "*", however, things are little different. We have to carry the value to multiply to the next level of recursion via parameter prevVal, where prevVal = prevVal * int(temp). Then, the new currSum should be currSum - prevVal + prevVal * int(temp), because we have added prevVal once in the last recursion and we need to remove it first before this recursion.

Java, JavaScript, C++, C#

The Java, JavaScript, C++, and C# solutions follow the same DFS approach as Python, with appropriate syntax changes for each language.

The key aspects to note are:

• For each character in 'num', we try the 3 possibilities, i.e., '+', '*' and '-'.
• The DFS function call is inside a for loop which runs over the length of the string 'num'.
• We also ensure not to split a number with a leading zero in non-single digit integers (e.g. "05" to "0" and "5").
• In the DFS function, we first check if the 'num' is empty and if the calculated value equals the target. If true, we add the 'path' to our answer list.

The base case for our DFS will be when we have traversed the entire length of the string 'num'.

While recursion may seem tricky at first, a careful analysis of the problem statement can simplify the understanding. The more we practice similar problems, the better we can get in understanding and writing recursive algorithms.

Time and Space Complexities

The time complexity for this problem is O(N * 4^N) where N is the size of the input string. This time is required as in the worst case for each index we could have four different recursive calls – one for each operation, i.e., '+', '-', '*' and '' (no operation).

The space complexity for this problem is O(N). The only extra space that we're using is the space for the recursive stack (in terms of space complexity), and the depth of the recursion would be at most N in this case. Also, we are using constant space for storing each valid expression path, and hence our total space complexity is O(N).