text: class Solution {
  public:
      vector<string> addOperators(string num, int target) {
          vector<string> result;
          if (num.size() == 0) return result;
          findSolution(num, target, result, "", 0, 0, 0, ' ');
          return result;        
      }
  
      //DFS algorithm
      void findSolution(const string &num, const int target,
                  vector<string>& result, 
                  string solution,
                  int idx,
                  long long val,
                  long long prev,
                  char preop )
      {
  
          if (target == val && idx == num.size()){
              result.push_back(solution);
              return;
          }
          if (idx == num.size()) return;
  
          string n;
          long long v=0;
          for(int i=idx; i<num.size(); i++) {
              //get rid of the number which start by "0"
              //e.g.  "05" is not the case.
              if (n=="0") return;
  
              n = n + num[i];
              v = v*10 + num[i]-'0';
  
              if (solution.size()==0){ 
                  findSolution(num, target, result, n, i+1, v, 0, ' ');
              }else{
                  // '+' or '-' needn't to adjust the priority
                  findSolution(num, target, result, solution + '+' + n, i+1, val+v, v, '+');
                  findSolution(num, target, result, solution + '-' + n, i+1, val-v, v, '-');
                  if (preop=='+') {
                      findSolution(num, target, result, solution + '*' + n, i+1, (val-prev)+prev*v, prev*v, preop);
                  }else if (preop=='-'){
                      findSolution(num, target, result, solution + '*' + n, i+1, (val+prev)-prev*v, prev*v, preop);
                  }else {
                      findSolution(num, target, result, solution + '*' + n, i+1, val*v, v, '*');
                  }
              }
          }
  
      }
  };
  