<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 ans = "";
    int g_v = -1;

    void backtracking(vector<int>& arr, const int idx)
    {
        if (idx == 4)
        {
            const int a = arr[0];
            const int b = arr[1];
            const int c = arr[2];
            const int d = arr[3];

            const int subv1 = a * 10 + b;
            const int subv2 = c * 10 + d;

            if (subv1 >= 24 || subv2 >= 60) return;

            const int v = 60 * (subv1) + subv2;
            if (v > g_v)
            {
                g_v = v;

                string str1 =  to_string(subv1);
                if (str1.size() < 2)
                {
                    str1 = "0" + str1;
                }

                string str2 = to_string(subv2);
                if (str2.size() < 2)
                {
                    str2 = "0" + str2;
                }
                ans = str1 + ":" + str2;
            }
            return;
        }

        array<bool, 10> seen;
        fill(seen.begin(), seen.end(), false);
        for (int i = idx; i < 4; ++i)
        {
            if (seen[arr[i]])
            {
                continue;
            }
            seen[arr[i]] = true;

            swap(arr[i], arr[idx]);
            backtracking(arr, idx + 1);
            swap(arr[i], arr[idx]);
        }
    }

    string largestTimeFromDigits(vector<int>& arr) {
        backtracking(arr, 0);
        return ans;
    }
};
12500