Expression Add Operators ----with +/- Facebook 真题

 // intput string: "123"  

// target = 6 

// operators: + / -

// {{1+2+3}}  // "1+(2+3)" NO

// "12-3"  if target = 9

A:

// VM[0]   {1-->"1"}  
// VM[1]   {12->"12",   3->"1+2",  -1-> "1-2" }
// VM[2]   { 123->'123"      with itself
      //   24-> "1+23",  -22->"1-23"  ,   // combine 23  pre = VM[0]
      //  15-> "12+3"   9->"12-3" ,  6-> "1+2+3" 0 -> "1+2-3"     4->"1-2+3"    -5->"1-3-3"}    // 3 comibine VM[1]

vector<string> allPerm(string str, int target) {
    int n = str.length();
    vector< unordered_map<int, vector<string>>>  VM(n, unordered_map<int, vector<string>>());
    if (str.length() == 0) {
        return vector<string>{};
    }
    for (int i = 0; i < n; i++) {
        for (int start = 0; start <= i; start++) {
            string curStr = str.substr(start, i - start + 1);
            if (curStr.length() > 1 && curStr[0] == '0') // incase we have "00" as a candidate
                continue;
            int curVal = stoi(curStr);
            if (start == 0) {
                VM[i][curVal].push_back(curStr);
            }
            else {
                auto pre = VM[start - 1];
                for (auto iter = pre.begin(); iter != pre.end(); iter++) {
                    int preVal = iter->first;
                    vector<string>& preStrs = iter->second;
                    for (auto tmp : preStrs) {
                        VM[i][preVal + curVal].push_back(tmp + "+" + curStr);
                        VM[i][preVal - curVal].push_back(tmp + "-" + curStr);
                    }
                }
            }
        }
    }
    return VM[n - 1][target];
}