My C++ 183ms solution

• ``````vector<string> addOperatorsWorker(vector<int>::const_iterator I,
vector<int>::const_iterator E,
const int64_t target, const char lowOpr,
const int64_t low, const int64_t high) {
vector<string> results;
int64_t n = 0;
for (auto i = I; i < E; ++i) {
// Prevent "00...0" and "0x..x":
if (i != I && *I == 0)
continue;

n = n * 10LL + *i;
int64_t k = (lowOpr == '+') ? (low + n * high) : (low - n * high);
if (i == E - 1) {
if (target == k)
results.push_back(to_string(n));
} else {
// For +/-, compute the current accumulated result.
// Reset the high-precedence operand.
for (auto &&r : addOperatorsWorker(i + 1, E, target, '+', k, 1))
results.push_back(to_string(n) + '+' + r);
for (auto &&r : addOperatorsWorker(i + 1, E, target, '-', k, 1))
results.push_back(to_string(n) + '-' + r);

// For multiplication, just carry over low-precedence accumulated result.
// But, compute the hig-precedence operand now.
for (auto &&r : addOperatorsWorker(i + 1, E, target, lowOpr, low, n * high))
results.push_back(to_string(n) + '*' + r);
}
}

return results;
}

vector<string> addOperators(string num, int target) {
if (num.length() == 0)
return {};

// Expand to a digit vector.
vector<int> N;
for (char c : num)
N.push_back(c - '0');

// "+ 0" and "* 1" for the starting condition; doesn't alter the value.
return addOperatorsWorker(N.cbegin(), N.cend(), target, '+', 0, 1);
}
``````

The basic idea is (1) call recursively from the left to right; (2) concatenate operands (e.g., gluing `1` and `2` into `12`). One caveat is disregarding `000...0` and `0x..z` cases.

The challenge is `+`, `-`, and `*` are left associative. We cannot simply take the result of the right hand side. To keep the left associativity, I'm passing two intermediate results: (1) low-precedence result; (2) high-precedence result.

Regarding the final result building, I didn't pass `vector<string>` and `string`. Contrary to intuition, returning sub-results of `vector<string>` and using `for` yield better performance. I used `&&` to eliminate any copy of sub results.

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