60-第k个排列

给出集合 [1,2,3,…,*n*]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，给定 n 和 k，返回第 k 个排列。

当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. `”321”

说明：

• 给定 n 的范围是 [1, 9]。
• 给定 k 的范围是[1, n!]。

---

示例

示例 1:

输入: n = 3, k = 3
输出: "213"

示例 2:

输入: n = 4, k = 9
输出: "2314"

---

解法

核心思想：回溯算法+剪枝

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        # 阶乘表
        fac = [1,1,2,6,24,120,720,5040,40320,362880]
        nums = [i for i in range(1, n + 1)]
        # 回溯函数
        def backTrack(nums,tmp, k):
            if not nums:
                return tmp
            for i in range(len(nums)):
                if fac[len(nums)-1] < k:
                    k -= fac[len(nums)-1]
                    continue
                return backTrack(nums[:i]+nums[i+1:], tmp+str(nums[i]), k)
        return backTrack(nums,"", k)

---

相关信息

LeetCode：Discussion | Solution