Given a string that contains only digits`0-9`and a target value, return all possibilities to add binary operators (not unary)`+`,`-`, or`*`between the digits so they evaluate to the target value.

Example 1:

``````Input:
num = "123",
target= 6

Output: ["1+2+3", "1*2*3"]
``````

Example 2:

``````Input:
num = "232",
target = 8

Output: ["2*3+2", "2+3*2"]
``````

Example 3:

``````Input:
num = "105",
target = 5

Output: ["1*0+5","10-5"]
``````

Example 4:

``````Input:
num = "00",
target = 0

Output: ["0+0", "0-0", "0*0"]
``````

Example 5:

``````Input:
num = "3456237490",
target = 9191

Output: []
``````

Thoughts:

1. DFS: expanding each level:

1. from curDepth to the end of the string, first extract the operand:

2. if num[curDepth] == '0', stop further expanding since we do not want a number with leading 0's

3. if current level is 0, then expanding it as the first operator

4. otherwise: expanding by appending the ['+', '-', '*'] at the end

Code

``````class Solution {
public List<String> addOperators(String num, int target) {
List<String> ans = new ArrayList<>();
if(num == null || num.length()== 0) return ans;
dfs(ans, num, "", target, 0, 0, 0);
return ans;
}
private void dfs(List<String> ans, String num,  String path, int target, int depth, long eval, long lastAdd){
if(depth == num.length()){
return;
}

for(int i = depth; i < num.length(); i++){
// substring the operand, excluding the leading '0' ones
if(i > depth && num.charAt(depth) == '0') break;
long cur = Long.parseLong(num.substring(depth, i + 1)); //[depth... i]
// global first operand
if(depth == 0){
dfs(ans, num , Long.toString(cur), target, i + 1, cur, cur); // leading element
}
else{
dfs(ans,num,path + "+" + cur, target, i + 1, eval + cur, cur);
//subtract
dfs(ans,num,path + "-" + cur, target, i + 1, eval - cur, -cur);
//multiply
dfs(ans,num,path + "*" + cur, target, i + 1, eval - lastAdd + lastAdd * cur, lastAdd * cur);
}
}
}
}
``````