# LeetCode Permutation Sequence

LeetCode 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):

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"`
6. `"321"`

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

```class Solution {
public:
vector<int> fact(int n) {
vector<int> vFact;
vFact.push_back(1); // 0!=1
int ans = 1;
for (int i = 1; i <= n; i++) {
ans *= i;
vFact.push_back(ans);
}
return vFact;
}
char work(string& candidates, vector<int>& vFact, int& k) {
int tmp = vFact[candidates.size() - 1];
int idx = ceil(k / float(tmp));
idx--;
char ans = candidates[idx];
candidates.erase(idx, 1);
k -= idx*tmp;
return ans;
}
string getPermutation(int n, int k) {
vector<int> vFact = fact(n);
string candidates = string("123456789").substr(0, n);
string ans(n, ' ');
for (int i = 0; i < n; i++)
ans[i] = work(candidates, vFact, k);
return ans;
}
};
```