题目链接：Permutation Sequence
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 (ie, for n = 3):
- “123”
- “132”
- “213”
- “231”
- “312”
- “321”
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
这道题的要求是返回由n个数排列组成的第k个序列（n范围是1~9）。
这道题的标签有回溯和数学，可是试了下回溯生成第k个（k已经对n!取模了）序列，超时。又试了试next_permutation函数，还是超时。。。不知道用回溯怎么做这道题。。。
不过，这确实是一道地地道道的数学问题。考虑到n个不同数的排列总共有n!种，也就是n-1个数的排列共有(n-1)!种，所以n个数的第k个排列的第一位数字取决于k中包含多少个(n-1)!，即k / (n-1)!。以此类推，第i位上的数字就是剩余k / (n-1-i)!位置上的数字（剩余k是由于k每次对(n-1-i)!取模）。所以只要当前的k除以(n-1-i)!，得到的数字就是当前剩余数组的位置的索引j。接下来取出该位置元素，并将该位置于i之间的元素都后移1个位置即可。
实现的时候，k首先需要减1，因为第1个已经生成了，也就是要在第1个的基础上生成第k-1个排列。而用f记录n!。
时间复杂度：O(n2)
空间复杂度：O(n)
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
class Solution
{
public:
string getPermutation(int n, int k)
{
string s(n, '0');
int i, j, f = 1;
for(i = 0; i < n; ++ i)
{
s[i] += i + 1;
f *= i + 1;
}
for(i = 0, k = (k - 1) % f; i < n; ++ i, k %= f)
{
f /= n - i;
int j = i + k / f;
char c = s[j];
while(j > i)
s[j] = s[-- j];
s[i] = c;
}
return s;
}
};