Additive Number LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool isAdditiveNumber(string num) {
4
    vector<string> adds;
5
    return backtrack(num, 0, adds);
6
  }
7

8
 private:
9
  bool backtrack(string num, int start, vector<string> &adds) {
10
    if (start >= num.size() && adds.size() >= 3) return true;
11

12
    int maxSize = num[start] == '0' ? 1 : num.size() - start;
13
    for (int i = 1; i <= maxSize; i++) {
14
      string current = num.substr(start, i);
15

16
      if (adds.size() >= 2) {
17
        string num1 = adds[adds.size() - 1], num2 = adds[adds.size() - 2];
18
        string sum = add(num1, num2);
19
        if (sum != current) continue;
20
      }
21

22
      adds.push_back(current);
23
      if (backtrack(num, start + i, adds)) return true;
24
      adds.pop_back();
25
    }
26
    return false;
27
  }
28

29
  string add(string num1, string num2) {
30
    string sum;
31
    int i1 = num1.size() - 1, i2 = num2.size() - 1, carry = 0;
32
    while (i1 >= 0 || i2 >= 0) {
33
      int current = carry + (i1 >= 0 ? (num1[i1--] - '0') : 0) + (i2 >= 0 ? (num2[i2--] - '0') : 0);
34
      carry = current / 10;
35
      sum.push_back(current % 10 + '0');
36
    }
37
    if (carry) sum.push_back(carry + '0');
38
    reverse(begin(sum), end(sum));
39
    return sum;
40
  }
41
};