题目
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"
给定 n 和 k，返回第 k 个排列。
示例 1：
输入：n = 3, k = 3
输出："213"示例 2：
输入：n = 4, k = 9
输出："2314"示例 3：
输入：n = 3, k = 1
输出："123"提示：
1 <= n <= 91 <= k <= n!
解答
思路
首先可以根据全排列树发现，第 iii 层的每个结点有(n - i)!个分支，对于每一层我们只需要找到第 j 个结点使得$j\times(n - i)! \ge k$，然后再$k=k−(j−1)×(n−i)!$ 再然后迭代下一层以此类推。 对于找第 j 个结点可以使用状态压缩，记录之前哪些点用过了。
class Solution {
public:
vector<int> fact; // 存储阶乘的数组
Solution(): fact(10) { // 构造函数，初始化fact数组为长度10的数组
fact[0] = 1; // 阶乘0的值为1
iota(fact.begin() + 1, fact.end(), 1); // 填充fact数组，从1到9
partial_sum(fact.begin(), fact.end(), fact.begin(), multiplies<int>()); // 计算部分和，得到1!到9!的值
}
string getPermutation(int n, int k) { // 返回第k个排列的字符串
string res; // 存储结果的字符串
int state = 0; // 表示已经使用的数字的状态
for (int i = n - 1; ~i; -- i) { // 从最高位到最低位遍历
int pre = 0; // 记录前一个状态下的排列数量
for (int j = 1; j <= n; ++ j) { // 遍历1到n
if (state >> j & 1) continue; // 如果数字已被使用，跳过
if (pre + fact[i] >= k) { // 如果前一个状态下的排列数量加上当前位的阶乘大于等于k
res.push_back(j + '0'); // 将当前数字加入结果字符串
k -= pre; // 更新k值
state |= 1 << j; // 更新已使用数字的状态
break; // 跳出内层循环
}
pre += fact[i]; // 更新前一个状态下的排列数量
}
}
return res; // 返回结果字符串
}
};