permutation sequence

class (object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        self.k = k
        self.res = ""
        self.dfs(n, [])
        return "".join([str(i) for i in self.res])
    
    def dfs(self, n, cur):
        if self.k >= 0:
            if len(cur) == n:
                self.k -= 1
                if self.k == 0:
                    self.res = cur[:]
                return
            for i in range(1, n+1):
                if i in cur:
                    continue
                cur.append(i)
                self.dfs(n, cur)
                cur.pop()

class (object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        
        # 1个数的permutations是1
        # 2个数的permutations是2
        # 3个数的permutations是3!
        # n个数的permutations是n！
        # 所以要找出第K个，首先确定最高位
        # 如果K是n!的倍数，那么最高位是 arr[K / n!-1] 否则最高位是 arr[K / n!]
        # 在arr中移除用过的数，更新k
        res = ""
        x = range(1, n+1)
        while n > 0:
            num = k / math.factorial(n-1)
            if k % math.factorial(n-1) == 0:
                num -= 1
            res += str(x[num])
            x.remove(x[num])
            k -= num * math.factorial(n-1)
            n -= 1
        return res