Number of Ways to Separate Numbers LeetCode solution in C++

1
class Solution {
2
 public:
3
  int helper(string &num, int idx, string last) {
4
    // If we have made it to the end of num we have found a valid sequence
5
    if (num.size() == idx) {
6
      return 1;
7
    }
8
    // The number of valid sequences starting from idx
9
    int count = 0;
10
    // If num[idx] == '0' then skip
11
    if (num[idx] != '0') {
12
      // Check all the possible numbers starting from idx
13
      for (int i = idx; i < num.size(); ++i) {
14
        // Construct the number
15
        string s = num.substr(idx, i - idx + 1);
16
        // If the number has less digits then the last number in the sequence it
17
        // can't be bigger
18
        if (s.size() < last.size()) {
19
          continue;
20
        }
21
        // If the number is bigger or equal than the last (needs the size check
22
        // as "3" > "20")
23
        if (last.size() < s.size() || s >= last) {
24
          // Do the recursice call  with idx = i+1 and last=s
25
          count += helper(num, i + 1, s);
26
        }
27
      }
28
    }
29
    return count;
30
  }
31

32
  int numberOfCombinations(string num) {
33
    return helper(num, 0, "0");
34
  }
35
};