<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 {
    int mh = -1;
    int mm = -1;
    void helper(vector<int>& arr, vector<bool>& vis, int ch, int cm, int rh, int rm) {
        if(rh==0 && rm==0) {
            if(ch<24 && cm<60) {
                if(ch>mh) {
                    mh = ch;
                    mm = cm;
                } else if(ch==mh) mm = max(mm, cm);
            }
            return;
        }
        for(int i=0;i<4;i++) {
            if(vis[i]==false) {
                if(rh>0) {
                    int nh = rh==2?(ch+arr[i]):(ch+arr[i]*10);
                    if(nh<24) {
                        vis[i] = true;
                        helper(arr,vis,nh,cm,rh-1,rm);
                        vis[i] = false;
                    }
                }
                if(rm>0) {
                    int nm = rm==2?(cm+arr[i]):(cm+arr[i]*10);
                    if(nm<60) {
                        vis[i] = true;
                        helper(arr,vis,ch,nm,rh,rm-1);
                        vis[i] = false;
                    }
                }
            }
        }
    }
public:
    string largestTimeFromDigits(vector<int>& arr) {
        vector<bool> vis(4,false);
        helper(arr,vis,0,0,2,2);
        if(mh==-1 || mm==-1) return "";
        string h = to_string(mh), m = to_string(mm);
        if(h.size()<2) h = '0'+h;
        if(m.size()<2) m = '0'+m;
        return h+':'+m;
    }
};
12600