# 282 Expression Add Operators

給一個string裡面都是數字，一個int target，在數字string中加入+,-,*，使總和變成target。

將可以總和成target的運算式存入List<String>中。

• Idea: 一看到題目初步想法是列出所有可能的數字組合、並在數字組合中插入所有可能的運算符號組合。

• Implementation: 實作上，可以用dfs recursion。這樣就可以把所有可能組合直接用argument記錄，不用額外空間儲存排列組合。 要注意處理乘法時，會有先乘除後加減的規則要處理，
  例如：1+3*4，會先得到1+3=4，但加上4之後，就需要做4-3 + 3*4的計算。
  另外，也要注意0開頭的數字是invalid的，例如0111這種直接不予計算。

• pseudocode:

          dfs, recursively call dfs function. 
          dfs():
          in each iteration, 
          check if this is the end of num, and sum == target, if yes, put into list.
          for each possibility of this new number,
            dfs() with +, dfs() with -, dfs() with *
  

• code:

  public class Solution {
      List<String> res = new ArrayList<>();
  
      public List<String> addOperators(String num, int target) {
          dfs(num, target, "", 0,0);
          return res;
      }
  
      void dfs(String num, int target, String str, long curSum, long prevNum){
          if(curSum == target && num.equals("")){
              res.add(str);
          }
  
          for(int i=1; i<=num.length(); i++){
              String curStr = num.substring(0,i);
  
              //number starts by 0 is invalid
              if(curStr.length() > 1 && curStr.charAt(0) == '0'){
                  return;
              }
  
              long curNum = Long.parseLong(curStr);
              String next = num.substring(i);
              if(!str.equals("")){
                  dfs(next, target, str+"*"+curStr, (curSum-prevNum)+prevNum*curNum, prevNum*curNum);
                  dfs(next, target, str+"+"+curStr, curSum+curNum, curNum);
                  dfs(next, target, str+"-"+curStr, curSum-curNum, -curNum);
              }else{
                  dfs(next, target, curStr, curNum, curNum);
              }
          }
      }
  }