@@ -0,0 +1,2040 @@
+package advanced.combinatorial.backtracking.dfs.lc282_expressionaddoperators;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A * Given a string that contains only digits 0-9 and a target value,%0A * return all possibilities to add binary operators (not unary) +, -, or * between the digits%0A * so they evaluate to the target value.%0A * Examples:%0A *  %22123%22, 6 -%3E %5B%221+2+3%22, %221*2*3%22%5D%0A *  %22232%22, 8 -%3E %5B%222*3+2%22, %222+3*2%22%5D%0A *  %22105%22, 5 -%3E %5B%221*0+5%22,%2210-5%22%5D%0A *  %2200%22, 0 -%3E %5B%220+0%22, %220-0%22, %220*0%22%5D%0A *  %223456237490%22, 9191 -%3E %5B%5D%0A */%0Apublic class Solution %7B%0A%0A    // My 2AC: T(N) = 3*T(N-1)%0A    public List%3CString%3E addOperators(String num, int target) %7B%0A        List%3CString%3E result = new ArrayList%3C%3E();%0A        doAddOperators(result, %22%22, num, target, 0, 0, 0);%0A        return result;%0A    %7D%0A%0A    // Don't add op for first num, try it after the first round in front of second,third... number%0A    private void doAddOperators(List%3CString%3E result, String path,%0A                                String str, int target,%0A                                int start, long eval, long mul) %7B%0A        if (start == str.length()) %7B%0A            if (eval == target) result.add(path);%0A            return;%0A        %7D%0A        for (int i = start; i %3C str.length(); i++) %7B%0A            if (i %3E start && str.charAt(start) == '0') break;       // error2: prevent %22105%22 -%3E %221%22 and %2205%22%0A            long num = Long.valueOf(str.substring(start, i + 1));%0A            if (start == 0) %7B                                       // error1: start=0 means first num, not i=1%0A                doAddOperators(result, String.valueOf(num), str, target, i + 1, num, num);%0A            %7D else %7B%0A                doAddOperators(result, path + %22+%22 + num, str, target, i + 1, eval + num, num);%0A                doAddOperators(result, path + %22-%22 + num, str, target, i + 1, eval - num, -num);                 // Recover eval%0A                doAddOperators(result, path + %22*%22 + num, str, target, i + 1, eval - mul + mul * num, mul * num); // Very smart about the mul handle%0A            %7D%0A        %7D%0A    %7D%0A%0A%7D%0A

leetcode-282 expression add operators