60. Permutation Sequence

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        # time O(N^2) space O(N)
        # edge case n=0
        if n == 0:
            return ""
            
        used = [False for _ in range(n+1)]
        path = []
        # cache factorial number 
        factorial = [1 for _ in range(n+1)]
        for i in range(2,n+1):
            factorial[i] = factorial[i-1]*i
        
        def dfs(n,k,idx,path):
            if idx == n :
                return
            # start with lowest number at highest position, check if following numbers' permunation bigger than k, if yes => means kth number exists in the remaining permutation.
                 #keep insert current smallest number into path ; 
    #   if no, means smallest number shouldn't be at the highest position, i += 1, skip permutation starting with least highest number by k -= cnt  
            cnt = factorial[n-1-idx]
            for i in range(1,n+1):
                if used[i]:
                    continue
                if cnt < k :
                    k-=cnt
                    continue
                path.append(i)
                used[i] = True
                dfs(n,k,idx+1,path) # here can't use path+[i] since it's not really backtracking(taking back number i )
                return 
        dfs(n,k,0,path)
        # convert path array into string 
        return ''.join([str(num) for num in path])