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.

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

Solution
Got TLE error.

class Solution {
public:
    unordered_map<int, vector<string>> helper(string num) {
        int n = num.size();
        unordered_map<int, vector<string>> res;
        for ( int i = 1; i <= n-1; i++ ) {
            int number = stol(num.substr(0, i));
            auto tmp_res = helper(num.substr(i));
            for ( auto j: tmp_res ) {
                int nj = j.second.size();
                for (int k = 0; k < nj; k++ ) res[number*j.first].push_back(num.substr(0, i) + "*" + j.second[k]);
            }
        }
        if ( num[0] != '0' or ( num[0] == '0' and stol(num) == 0 )) res[stol(num)].push_back(num);
        return res;
    }
    vector<string> addOperators(string num, int target) {
        int n = num.size();
        vector<string> res;
        if ( n == 0 )  return res;
        auto tmp_res = helper(num);
        for ( auto j: tmp_res ) {
            if ( j.first == target ) res = j.second;
        }

        for ( int i = 1; i <= n-1; i++ ) {
            auto tmp_res = helper(num.substr(0, i));
            for ( auto j: tmp_res ) {
                int number = j.first, nj = j.second.size();
                vector<string> res1 = addOperators(num.substr(i), target - number);
                vector<string> res2 = addOperators(num.substr(i), number - target);
                for ( int i1 = 0; i1 < int(res1.size()); i1++ ) {
                    for ( int jj = 0; jj < nj; jj++ ) {
                        res.push_back(j.second[jj] + "+" + res1[i1]);
                    }
                }
                for ( int i2 = 0; i2 < int(res2.size()); i2++ ) {
                    for ( int jj = 0; jj < nj; jj++ ) {
                        res.push_back(j.second[jj] + "-" + res2[i2]);
                    }
                }
            }
        }
        return res;
    }
};

Use a 2D matrix to save time?

class Solution {
  public:
    string opposite(string s) {
      string res;
      for ( int i = 0; i < int(s.size()); i++) {
        char c = s[i];
        if ( c == '+' ) res += "-";
        if ( c == '-' ) res += "+";
        if ( c != '+' and c != '-' ) res += c;
      }
      return res;

    }
    vector<string> addOperators(string num, int target) {
      vector<string> res;
      int n = num.size();
      if ( n == 0 ) return res;
      vector<vector<unordered_map<int, vector<string> > > > record(n, vector<unordered_map<int, vector<string> > >(n));
      for ( int i = 0; i < n; i++ ) record[i][i][stol(num.substr(i, 1))].push_back(num.substr(i, 1));
      for ( int j = 2; j <= n; j++ ) {
        for ( int i = 0; i < n-j+1; i++ ) {
          for ( int ii = 1; ii <= j-1; ii++ ) {
            int num1 = stol(num.substr(i, ii));
            if ( num1 == 0 and ii != 1 ) continue;
            if ( num1 != 0 and num[i] == '0' ) continue;
            for ( auto rr2: record[i+ii][i+j-1] ) {
              int num2 = rr2.first;
              for ( int i2 = 0; i2 < int(rr2.second.size()); i2++ ) {
                record[i][i+j-1][num1*num2].push_back(num.substr(i, ii) + "*" + rr2.second[i2]);
              }
            }
          }
          if ( num[i] != '0' ) record[i][i+j-1][stol(num.substr(i, j))].push_back(num.substr(i, j));
        }
      }
      for ( int i = n-2; i >= 0; i-- ) {
        // length = n-i
        for ( int j = 1; j <= n-i-1; j++ ) {
          for ( auto rr1: record[i][i+j-1] ) {
            for ( auto rr2: record[i+j][n-1] ) {
              int num1 = rr1.first, num2 = rr2.first;
              for ( int i1 = 0; i1 < int(rr1.second.size()); i1++ ) {
                for ( int i2 = 0; i2 < int(rr2.second.size()); i2++ ) {
                  record[i][n-1][num1+num2].push_back(rr1.second[i1] + "+" + rr2.second[i2]);
                  record[i][n-1][num1-num2].push_back(rr1.second[i1] + "-" + opposite(rr2.second[i2]));
                }
              }
            }
          }
        }
      }
      if ( record[0][n-1].find(target) != record[0][n-1].end() ) res = record[0][n-1][target];
      return res;
    }
};

TLE again...

class Solution {
  public:
    void help(string num, long target, long prev, string tmp, vector<string>& res) {
      int n = num.size();
      if ( n == 0 and target == 0 ) res.push_back(tmp);
      for ( int i = 1; i <= n; i++ ) {
        long num1 = stol(num.substr(0, i));
        if ( i != 1 and num[0] == '0' ) return;
        if ( tmp == "" ) help(num.substr(i), target - num1, num1,  num.substr(0, i), res);
        else {
          help(num.substr(i), target - num1, num1, tmp + "+" + num.substr(0, i), res);
          help(num.substr(i), target + num1, -num1, tmp + "-" + num.substr(0, i), res);
          help(num.substr(i), target + prev - prev*num1, prev*num1, tmp + "*" + num.substr(0, i), res);
        }
      }
      return;
    }
    vector<string> addOperators(string num, int target) {
      vector<string> res;
      help(num, target, 0, "", res);
      return res;
    }
};

Notes
无话可说，搜到的smart solution太厉害了。这里的关键是，处理到一个数的时候，考虑这个数之前符号的情况。

• 如果num1前是+，那么剩下字符串的目标值是target-num1。
• 如果num1前是-，那么剩下字符串的目标值是target+num1。
• 乘法是比较复杂，需要记录一个prev，代表连乘到num1前的值。如果num1是*，那么num1就和这个值相乘，而剩下字符串的目标值为target + prev - num1*prev。
  非常neat的一个解法，注意体会。