Expression Add Operators LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<string> res;
4
  string s;
5
  int target, n;
6
  void solve(int it, string path, long long resSoFar, long long prev) {
7
    if (it == n) {
8
      if (resSoFar == target) res.push_back(path);
9
      return;
10
    }
11
    long long num = 0;
12
    string tmp;
13

14
    for (auto j = it; j < n; j++) {
15
      if (j > it && s[it] == '0') break;
16

17
      num = num * 10 + (s[j] - '0');
18
      tmp.push_back(s[j]);
19

20
      if (it == 0)
21
        solve(j + 1, tmp, num, num);
22
      else {
23
        solve(j + 1, path + "+" + tmp, resSoFar + num, num);
24
        solve(j + 1, path + '-' + tmp, resSoFar - num, -num);
25
        solve(j + 1, path + '*' + tmp, resSoFar - prev + prev * num, prev * num);
26
      }
27
    }
28
  }
29
  vector<string> addOperators(string num, int target) {
30
    this->target = target;
31
    s = num, n = num.size();
32

33
    solve(0, "", 0, 0);
34
    return res;
35
  }
36
};