题目描述
给出集合 [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”
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法1：回溯+剪枝
思路：
明显的回溯题，一开始自信满满写了个回溯模板，一提交，TL出现，
思考：我们没有进行剪枝优化，
1.每次进入一个新的分支时，我们判断这个分支的叶子节点数是否大于k，如果小于k表示这个分支的所有的排列都不是我们要的第k个排列，我们就进行剪枝，让k=k-这个分支叶子节点数，然后判断下一个分支。循环重复，找到第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
| class Solution {
public:
string getPermutation(int n, int k) {
vector<bool> used(n,false);
int count=0;
string temp;
int factorial[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
m=false;
search(k,used,n,count,temp,factorial);
return res;
}
void search(int k,vector<bool> &used,int n,int count,string temp,int factorial[])
{
if(count==n)
{
m=true;
res=temp;
return ;
}
int p=factorial[n-1-count];
int i;
for(i=0;i<n;i++)
{
if(used[i])
continue;
if(p<k)
{
k-=p;
continue;
}
used[i]=true;
char ch='0'+i+1;
search(k,used,n,count+1,temp+ch,factorial);
if(m)
break;
}
return ;
}
private:
string res;
bool m;
};
|