282. Expression Add Operators

Given a string that contains only digits0-9and 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()){
            if(eval == target) ans.add(path);
            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{
                //add
                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);
            }
        }
    }
}