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", "123"]
Example 2:

Input: num = "232", target = 8
Output: ["23+2", "2+32"]
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: []

class Solution {
    public List addOperators(String num, int target) {
        List res = new ArrayList<>();
        if (num == null || num.length() == 0) return res;
        dfs(num, "", 0, target, res, 0, 0);
        return res;
    }
    
    private void dfs(String num, String temp, int index, int target, List res, long val, long multi) {
        if (index == num.length()) {
            if (val == target) res.add(temp);
            return;
        }
        for (int i = index; i < num.length(); i++) {
            if (i != index && num.charAt(index) == "0") break;
            
            long cur = Long.parseLong(num.substring(index, i+1));
            if (index == 0) {
                dfs(num, temp+cur, i+1, target, res, cur, cur);
            } else {
                dfs(num, temp+"+"+cur, i+1, target, res, val+cur, cur);
                dfs(num, temp+"-"+cur, i+1, target, res, val-cur, -cur);
                dfs(num, temp+"*"+cur, i+1, target, res, val-multi+multi*cur, multi*cur);
            }
        }
    }
}

class Solution {
    public List addOperators(String num, int target) {
        List res = new ArrayList<>();
        dfs(num, 0, 0, target, 0, new StringBuilder(), res);
        return res;
    }
    private void dfs(String num, int index, long value, int target, long multi, StringBuilder sb, List res) {
        if (index == num.length()) {
            if (value == target) res.add(sb.toString());
            return;
        }
        for (int i = index; i < num.length(); i++) {
            if (num.charAt(index) == "0" && i != index) break;
            long cur = Long.parseLong(num.substring(index, i+1));
            int len = sb.length();
            if (index == 0) {
                sb.append(cur);
                dfs(num, i+1, cur, target, cur, sb, res);
                sb.setLength(len);
            } else {
                sb.append("+").append(cur);
                dfs(num, i+1, value+cur, target, cur, sb, res);
                sb.setLength(len);
                
                sb.append("-").append(cur);
                dfs(num, i+1, value-cur, target, -cur, sb, res);
                sb.setLength(len);
                
                sb.append("*").append(cur);
                dfs(num, i+1, value-multi+multi*cur, target, multi*cur, sb, res);
                sb.setLength(len);
            }
        }
    }
}

class Solution {
    public List addOperators(String num, int target) {
        List res = new ArrayList<>();
        dfs(num.toCharArray(), 0, new StringBuilder(), 0, 0, target, res);
        return res;
    }
    private void dfs(char[] digits, int index, StringBuilder sb, long value, long multi, int target, List res) {
        if (index == digits.length) {
            if (value == target) res.add(sb.toString());
            return;
        }
        for (int i = index; i < digits.length; i++) {
            if (digits[index] == "0" && i != index) break;
            long cur = Long.parseLong(new String(digits, index, i-index+1));
            int len = sb.length();
            if (index == 0) {
                sb.append(cur);
                dfs(digits, i+1, sb, cur, cur, target, res);
                sb.setLength(len);
            } else {
                sb.append("+").append(cur);
                dfs(digits, i+1, sb, value+cur, cur, target, res);
                sb.setLength(len);
                
                sb.append("-").append(cur);
                dfs(digits, i+1, sb, value-cur, -cur, target, res);
                sb.setLength(len);
                
                sb.append("*").append(cur);
                dfs(digits, i+1, sb, value-multi+multi*cur, multi*cur, target, res);
                sb.setLength(len);
            }
        }
    }
}