Leetcode/G家F家 -- 282. Expression Add Operators(backtracking)

282. Expression Add Operators(backtracking)

• Difficulty: Hard

https://leetcode.com/problems/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.

Examples: 

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

-------------------------------------------------
multed(apply only for multiplication) is the number you add from last calculation.
When multiply, to use the digit from last result, we need to minus what we have added last time(multed), then add it with the new calculation with current digit(multed*cur).cur is the current single digit in num.

Eg: (12345)
1+2+3 (we added 3 in this round) multed =3
1+2+3-(3)+3*4(we did *4, so we minus 3 from last result and add new calc: 3(last multed)*4(cur)
                          so new multed = 3*4)
1+2+3-3+3*4-(3*4)+(3*4)*5(we did *5, last multed = (3*4), cur =5)

So we conclude for sum when doing *:  newsum = sum - multed + (multed*cur)
                                                                                             last              new

参考： https://discuss.leetcode.com/topic/24523/java-standard-backtrace-ac-solutoin-short-and-clear
思路：

*   Use long to avoid overflow

 * 0 sequence: because we can't have numbers with multiple digits started with zero, we have to deal with it too.(error case: see below code)   
//if not have it, will keep loop getting fail   case1:105(5),get (1*5) bc we have case of merging 05 not containg 0;

*For multiplication, we minus the sum from multed(what we added in last recursion) see above

*关键是：除了 + - *,we have the merge operation that's why for loop needed
Complexity: O(4^n)

T(n) = 3 * T(n-1) + 3 * T(n-2) + 3 * T(n-3) + ... + 3 *T(1);
T(n-1) = 3 * T(n-2) + 3 * T(n-3) + ... 3 * T(1);
Thus T(n) = 4T(n-1);

public class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<String>();
        if(num == null)return res;
        dfs(res, new StringBuilder(),num,target,0,0,0);
        return res;
    }
    public void dfs(List<String> res, StringBuilder sb,String num,int target,int index,long sum,long multed){
        if(index==num.length()){
            if(sum == target)res.add(sb.toString());
            return;
        }
        for(int i = index;i<num.length();i++){
            if(i!=index&&num.charAt(index)=='0')return;//0 sequence
             
            //fail case2:105(5),get(1*5)--index =1,i=2 substring(1,3)=05,long cur =5,sb.append(cur), so missing 0 
            int len = sb.length();
            long cur = Long.parseLong(num.substring(index,i+1));
            if(index == 0){
                dfs(res,sb.append(cur),num,target,i+1,cur,cur);//start from 0, sum + cur?work too since sum is 0
                sb.setLength(len);//need to setback since can merge number, else have duplicated: 110-5(eg: 105(5))
            }else{
                //3 options for each number
                dfs(res,sb.append("+").append(cur),num,target,i+1,sum+cur,cur);
                sb.setLength(len);//bc we append in sb, we need to setback for dfs
                dfs(res,sb.append("-").append(cur),num,target,i+1,sum-cur,-cur);
                sb.setLength(len);
                dfs(res,sb.append("*").append(cur),num,target,i+1,sum-multed+(multed*cur),multed*cur);
                sb.setLength(len);
            }
        }
        
    }
}