# 递归的方法，创建一个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

LinkCode 第k个排列