题目简介：
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"
给定 n 和 k，返回第 k 个排列。
说明：
- 给定 n 的范围是 [1, 9]。
- 给定 k 的范围是[1, n!]。
示例 1:
1
2
| 输入: n = 3, k = 3
输出: "213"
|
示例 2:
1
2
| 输入: n = 4, k = 9
输出: "2314"
|
思路：
深搜+回溯，需要注意的是需要剪枝，不然会超时。
我们先事先定义一个数组dp，dp[n]代表n个数字所能构成的排列数。
当给定的k > dp[n - count - 1]时(count为当前已选择的数字个数)，说明可以跳过该数字，直接进入下一个数字(减少时间)。
并且在回溯的时候可以放弃回溯，直接return，因为找的是第k个，所以后面的都不用去管了。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class Solution {
public:
vector<int> dp = vector<int>(10, 0);
string res;
vector<bool> used = vector<bool>(10, false);
void dfs(int n, int& k, int count, string& s){
if(count == n){
k--;
if(k == 0){
res = s;
return;
}
}
for(int i = 1; i <= n; i++){
if(used[i])
continue;
if(dp[n - count - 1] < k){
k = k - dp[n - count - 1];
continue;
}
s += (i + '0');
used[i] = true;
dfs(n, k, count + 1, s);
return;
}
}
string getPermutation(int n, int k) {
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
dp[i] = dp[i - 1] * i;
}
string s = "";
dfs(n, k, 0, s);
return res;
}
};
|
