## Description

The set [1,2,3,...,*n*] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

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

Given n and k, return the kth permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"


Example 2:

Input: n = 4, k = 9
Output: "2314"


## Solutions

### 1. Backtracking

全排会超时！

# Time: O(n^2)
# Space: O(n)
class Solution:
def getPermutation(self, n: int, k: int) -> str:
res = []
visited = set()
self.dfs(n, k, visited, '', res)
return res[k-1]

def dfs(self, n, k, visited, path, res):
# add this, TLE too
if k <= len(res):
return
if n == len(path):
res.append(path)
return

for i in range(1, n+1):
if i in visited:
continue
visited.add(i)
self.dfs(n, k, visited, path + str(i), res)
visited.remove(i)
# Time Limit Exceeded
# 85/200 cases passed (N/A)
# Testcase
# 9
# 331987


举个例子，n = 4，k = 9 时，有：

1234
1243
1324
1342
1423
1432
2134
2143
2314  <= k = 9
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321


根本不需要从 1 开始全排，因为从 1 开始全排的只有 3!=6 个数，那么这里可以优化！

# Time: O(n^2)
# Space: O(n)
class Solution:
def getPermutation(self, n: int, k: int) -> str:
self.k = k

def backtrack(path, remain):
if not remain:
self.k -= 1
if self.k == 0:
return path
return ''

for i in range(len(remain)):
if self.k > math.factorial(len(remain)-1):
self.k -= math.factorial(len(remain)-1)
continue
ans = backtrack(path + remain[i], remain[:i]+remain[i+1:])
if ans:
return ans
return ''
nums = list(map(str, range(1, n+1)))
return backtrack('', nums)
# 200/200 cases passed (32 ms)
# Your runtime beats 78.87 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)