Largest Multiple of Three LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> ans;
4

5
  void calculate(vector<int> &count, int no, vector<int> &temp) {
6
    if (no == 0) {
7
      int flag = 0, sum1 = 0, sum2 = 0, validSum = 0;
8
      for (int j = 1; j < 10; j++) {
9
        sum1 += temp[j];
10
        sum2 += ans[j];
11
        validSum += (temp[j] * j);
12
      }
13
      if (validSum % 3 != 0) {
14
        return;
15
      }
16

17
      if (sum2 > sum1)
18
        return;
19
      else if (sum1 > sum2) {
20
        for (int i = 1; i < 10; i++) {
21
          ans[i] = temp[i];
22
        }
23
        return;
24
      }
25
      int j = 9;
26
      while (j > 0) {
27
        if (ans[j] < temp[j]) {
28
          flag = 1;
29
          break;
30
        } else if (ans[j] > temp[j])
31
          break;
32
        j--;
33
      }
34
      if (flag == 1) {
35
        for (int i = 1; i < 10; i++) {
36
          ans[i] = temp[i];
37
        }
38
      }
39
      return;
40
    }
41

42
    int targetCount = count[no] - 2;
43

44
    if (targetCount < 0) targetCount = 0;
45

46
    int co = count[no];
47

48
    do {
49
      temp[no] = co;
50

51
      calculate(count, no - 1, temp);
52

53
      co--;
54
    } while (co >= targetCount);
55
  }
56

57
  string largestMultipleOfThree(vector<int> &digits) {
58
    vector<int> count(10, 0);
59
    int n = digits.size();
60
    for (int i = 0; i < n; i++) {
61
      count[digits[i]]++;
62
    }
63
    vector<int> temp(10, 0);
64
    ans.resize(10, 0);
65
    calculate(count, 9, temp);
66

67
    string res = "";
68
    ans[0] = count[0];
69
    for (int i = 9; i >= 0; i--) {
70
      for (int j = 1; j <= ans[i]; j++) {
71
        res += ('0' + i);
72
      }
73
    }
74
    if (res.size() >= 2 && res[0] == '0' && res[1] == '0') return "0";
75
    return res;
76
  }
77
};