<p>Given an array <code>arr</code> of 4 digits, find the latest 24-hour time that can be made using each digit <strong>exactly once</strong>.</p>

<p>24-hour times are formatted as <code>&quot;HH:MM&quot;</code>, where <code>HH</code> is between <code>00</code> and <code>23</code>, and <code>MM</code> is between <code>00</code> and <code>59</code>. The earliest 24-hour time is <code>00:00</code>, and the latest is <code>23:59</code>.</p>

<p>Return <em>the latest 24-hour time in <code>&quot;HH:MM&quot;</code> format</em>. If no valid time can be made, return an empty string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2,3,4]
<strong>Output:</strong> &quot;23:41&quot;
<strong>Explanation:</strong> The valid 24-hour times are &quot;12:34&quot;, &quot;12:43&quot;, &quot;13:24&quot;, &quot;13:42&quot;, &quot;14:23&quot;, &quot;14:32&quot;, &quot;21:34&quot;, &quot;21:43&quot;, &quot;23:14&quot;, and &quot;23:41&quot;. Of these times, &quot;23:41&quot; is the latest.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [5,5,5,5]
<strong>Output:</strong> &quot;&quot;
<strong>Explanation:</strong> There are no valid 24-hour times as &quot;55:55&quot; is not valid.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>arr.length == 4</code></li>
	<li><code>0 &lt;= arr[i] &lt;= 9</code></li>
</ul>

class Solution {
public:
    string largestTimeFromDigits(vector<int>& arr) {
        vector <vector <int>> permutations;
        getPermutations(arr, 0, permutations);
        sort(permutations.begin(), permutations.end());
        reverse(permutations.begin(), permutations.end());
        for (auto time : permutations) {
            if (isValidTime(time)) {
                return getTime(time);
            }
        }
        return "";
    }

    string getTime(vector <int> &digits) {
        return to_string(digits[0]) + to_string(digits[1])
            + ":" + to_string(digits[2]) + to_string(digits[3]);
    }

    bool isValidTime(vector <int> &digits) {
        int hour = digits[0] * 10 + digits[1];
        int minutes = digits[2] * 10 + digits[3];

        return (0 <= hour && hour <= 23
                && 0 <= minutes && minutes <= 59);
    }

    void getPermutations(vector <int> &arr, int start, vector <vector <int>> &permutations) {
        // printf("start=%d,perms=%d,", start, permutations.size());
        // cout << "Current : " << getTime(arr) << endl;
        if (start == arr.size() - 1) {
            cout << "Perm : " << getTime(arr) << endl;
            permutations.push_back(arr);
            return;
        }

        // swap with all possible elements to the right
        for (int i = start + 1; i < arr.size(); i++) {
            swap(arr[i], arr[start]);
            getPermutations(arr, start + 1, permutations);
            swap(arr[i], arr[start]);   // backtrack
        }

        // leave current element as it is
        getPermutations(arr, start + 1, permutations);
    }
};
14900