Largest Time for Given Digits LeetCode solution in C++

1
class Solution {
2
 public:
3
  string largestTimeFromDigits(vector<int> &arr) {
4
    sort(arr.rbegin(), arr.rend());
5
    used.resize(4);
6

7
    string ret = "";
8
    if (!dfs(arr, 0, 0))
9
      return ret;
10
    else {
11
      for (int i = 0; i < 2; i++) ret.push_back(ans[i] + '0');
12

13
      ret.push_back(':');
14

15
      for (int i = 2; i < 4; i++) ret.push_back(ans[i] + '0');
16
    }
17
    return ret;
18
  }
19

20
 private:
21
  vector<int> min = {600, 60, 10, 1};
22
  vector<int> ans;
23
  vector<int> used;
24
  bool dfs(const vector<int> &arr, int totalhour, int totalmin) {
25
    if (totalhour >= 24 * 60) return false;
26
    if (totalmin >= 60) return false;
27
    if (ans.size() == 4) return true;
28

29
    for (int i = 0; i < 4; i++) {
30
      if (used[i]) continue;
31
      used[i] = 1;
32

33
      int pos = ans.size();
34
      if (pos < 2)
35
        totalhour += arr[i] * min[pos];
36
      else
37
        totalmin += arr[i] * min[pos];
38

39
      ans.push_back(arr[i]);
40

41
      if (dfs(arr, totalhour, totalmin)) return true;
42

43
      if (pos < 2)
44
        totalhour -= arr[i] * min[pos];
45
      else
46
        totalmin -= arr[i] * min[pos];
47

48
      ans.pop_back();
49
      used[i] = 0;
50
    }
51

52
    return false;
53
  }
54
};