949 Largest Time for Given Digits

link: https://leetcode.com/problems/largest-time-for-given-digits/

Thought

Its easy to think use DFS to solve it: it has limit data(4 digits), and DFS will enumerates all possible combinations

Code

class Solution:
    def largestTimeFromDigits(self, A):
        """
        :type A: List[int]
        :rtype: str
        """
        self.res = -1
        def dfs(A, res, visited):
            if len(res) == 4:
                if res[0] * 10 + res[1] < 24 and res[2] * 10 + res[3] < 60:
                    self.res = max(self.res, res[0]* 1000 + res[1] * 100 + res[2] * 10 + res[3])
            for j in range(4):
                if not visited[j]:
                    visited[j] = True
                    res.append(A[j])
                    dfs(A,res, visited)
                    visited[j] = False
                    res.pop(-1)
        dfs(A, [], [False, False, False,False]) 
        if self.res == -1:
            return ""
        return str(self.res// 100).zfill(2) + ":" + str(self.res % 100).zfill(2)

Runtime

Time: O(n!)
Space: O(n!)