Thời gian lớn nhất từ 4 chữ số cho trước trong C++

Mô tả bài toán

Cho 4 chữ số, tìm thời gian hợp lệ lớn nhất theo định dạng 24h (HH:MM). Thời gian hợp lệ: 00:00 đến 23:59. Trả về chuỗi độ dài 5, hoặc rỗng nếu không có thời gian hợp lệ.

Ví dụ: [1,2,3,4] → "23:41".

Giải pháp (DFS + Kiểm tra hợp lệ)

• Sinh tất cả hoán vị 4 chữ số (DFS/backtracking).
• Kiểm tra hợp lệ: giờ ≤ 23, phút ≤ 59.
• Giữ thời gian lớn nhất theo thứ tự từ điển (string so sánh trực tiếp).

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

class Solution {
    bool isValid(const string& a) {
        if (a[0] > '2') return false;
        if (a[0] == '2' && a[1] > '3') return false;
        if (a[3] > '5') return false;
        return true;
    }
    void dfs(vector<int>& A, string& res, string& cur) {
        if (cur.size() == 5) {
            if (isValid(cur) && cur > res) res = cur;
            return;
        }
        for (int i = 0; i < 4; ++i) {
            if (A[i] != -1) {
                int tmp = A[i];
                cur += char(A[i] + '0');
                if (cur.size() == 2) cur += ':';
                A[i] = -1;
                dfs(A, res, cur);
                A[i] = tmp;
                cur.pop_back();
                if (cur.size() == 2) cur.pop_back();
            }
        }
    }
public:
    string largestTimeFromDigits(vector<int>& A) {
        string res = "", tmp = "";
        dfs(A, res, tmp);
        return res;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4};
    cout << ob.largestTimeFromDigits(v);
    return 0;
}

Đầu vào

{1,2,3,4}

Đầu ra

23:41