# C++ 3ms solution, divide and conquer + memoization

• ``````class Solution {
public:
vector<int>& diffWaysToCompute(unordered_map<int,vector<int>>& mm,
vector<int>& token, int first, int last) {
int key = first * ((int)token.size() + 1) + last;
if (mm.find(key) != mm.end())
return mm[key];

vector<int> res;

if (first + 1 == last) {
res.push_back(token[first]);
} else {
for (int i = first + 1; i < last; i += 2) {
vector<int>& l = diffWaysToCompute(mm, token, first, i);
vector<int>& r = diffWaysToCompute(mm, token, i + 1, last);
for (auto v1 : l) {
for (auto v2 : r) {
switch (token[i]) {
case '+': res.push_back(v1 + v2); break;
case '-': res.push_back(v1 - v2); break;
case '*': res.push_back(v1 * v2); break;
}
}
}
}
}

return mm[key] = std::move(res);
}

vector<int> diffWaysToCompute(string input) {
vector<int> token;
unordered_map<int,vector<int>> mm;

int v = 0;
for (auto ch : input) {
if (isdigit(ch))
v = v * 10 + (ch - '0');
else {
token.push_back(v);
token.push_back(ch);
v = 0;
}
}
token.push_back(v);

vector<int>& res = diffWaysToCompute(mm, token, 0, (int)token.size());
sort(res.begin(), res.end());

return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.