# 递归的方法，创建一个visit判断此值是否已经添加过，每一层不断地循环，加入没有被访问的元素，直到最后结果的长度满足要求加入答案中

class Solution:

    """

    @param n: n

    @param k: the k-th permutation

    @return: a string, the k-th permutation

    """

    def getPermutation(self, n, k):

        nums = [x for x in range(1, n + 1)]

        visit = [0 for i in range(n)]

        self.ret = []

        self._permute(nums, visit, 0, [])

        # 因为结果要返回字符串类型，所以对数字类型进行处理

        ans = [str(j) for j in self.ret[k-1]]

        return "".join(ans)

    def _permute(self, nums, visit, count, ret):

        if count == len(nums):

            self.ret.append(ret)

            return

        for i in range(len(nums)):

            if visit[i] == 0:

                # ret += [nums[i]]  容易出错，如果加入这句后面需要还原，不然影响后面的循环

                visit[i] = 1

                self._permute(nums, visit, count + 1, ret + [nums[i]])

                visit[i] = 0