给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。示例 1:
输入: n = 3, k = 3 输出: "213"示例 2:
输入: n = 4, k = 9 输出: "2314"思路：
每次循环根据k的大小可以确定第一位数，
举例，设n = 3， k = 1， 此时第一位数只可能是1， 2， 3，而且一共有3！ = 6种结果，所以每个数开头对应两种结果
当k = 1或2时，对应的第一位就是1，
当k = 3或4时，对应2，
当k = 5或6时，对应3，
以此类推，可以不断确定第一位的结果。
import math class Solution(object): def getPermutation(self, n, k): """ :type n: int :type k: int :rtype: str """ digit = [i for i in range(1, n + 1)] #生成1 ~ n的列表 res = "" while n > 0: tmp = math.factorial(n - 1) #计算一共有多少种组合 idx = (k - 1) / tmp #由K在tmp中占的比例来确定第一位的数字 k -= idx * tmp #第一位确定之后，刷新k res += str(digit[idx]) digit.pop(idx) n -= 1 return res或者递归：
class Solution(object): def getPermutation(self, n, k): """ :type n: int :type k: int :rtype: str """ fac = [1] for i in range(2, n + 1): fac.append(fac[-1] * i) digits = [i for i in range(1, n + 1)] self.res = "" def dfs(left_digit, tmp, kk): if left_digit == 0: self.res = tmp[:] return for digit in digits: kk -= fac[left_digit - 2] if kk <= 0: kk += fac[left_digit - 2] fac.pop() digits.remove(digit) dfs(left_digit - 1, tmp + str(digit), kk) break dfs(n, "", k) return self.res
