282 Expression Add Operators

282. Expression Add Operators

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: []

---

-------------------------
典型的dfs。
唯一的难点在“巧妙”地处理参数cut, 可以运用到arithmetic evaluation题型
credit: https://leetcode.com/problems/expression-add-operators/discuss/71895/Java-Standard-Backtrace-AC-Solutoin-short-and-clear

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