# 60. 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 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.
- Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
# Solution
Approach 1: Level-by-level.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
private:
vector<bool> bitMap;
int getFactorial(int n) {
if (n <= 1) return 1;
return n * getFactorial(n - 1);
}
void getPermutation(int n, int k, string& seq) {
if (n == 0)
return;
int f = getFactorial(n - 1);
int i = (k - 1) / f;
int j = -1;
for (int k = 0; k <= i; ++k)
{
j++;
while (bitMap[j])
j++;
}
bitMap[j] = true;
seq += ('1' + j);
getPermutation(n - 1, (k - 1) % f + 1, seq);
}
public:
string getPermutation(int n, int k) {
string seq = "";
bitMap = vector<bool>(n, false);
getPermutation(n, k, seq);
return seq;
}
};
class Solution {
public:
string getPermutation(int n, int k) {
ostringstream seq;
vector<int> nums;
int f = 1;
for (int i = 1; i <= n; ++i)
{
nums.push_back(i);
f *= i;
}
for (int i = n; i >= 1; --i)
{
f /= i;
int pos = (k - 1) / f;
seq << nums[pos];
nums.erase(nums.begin() + pos);
k = (k - 1) % f + 1;
}
return seq.str();
}
};