```
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.