思路：确定了 a1 后，这些排列从编号 (a1−1)⋅(n−1)! 开始，到 a1⋅(n−1)! 结束，总计 (n−1)! 个，因此第 k 个排列实际上就对应着这其中的第 k′=(k−1)mod(n−1)!+1 个排列。这样一来，我们就把原问题转化成了一个完全相同但规模减少 1 的子问题：求 [1,n]\a1 这 n−1 个元素组成的排列中，第 k′ 小的排列。
string getPermutation(int n, int k) {
vector<int> factorials = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
vector<int> nums(n, 0);
iota(std::begin(nums), std::end(nums), 1);
string ret;
k --; // 从第 0 个开始
for(int i = n - 1; i >= 0; i --){
auto it = nums.begin() + k / factorials[i];
ret += ('0' + *it);
nums.erase(it);
k %= factorials[i];
}
return ret;
}
