I use cantor expansion to solve this problem in O(n^2) time complex, and was accept. But when I test a case with K greater than n! in my PC, I got a wrong answer. see the commented line. Even I commented that line, OJ accepted my answer.

```
class Solution {
public:
string getPermutation(int n, int k) {
--k;
//k %= factorial(n); // OJ accepted the answer without this line.
string str;
for (int i = 0 ; i< n; ++i){
str += (i + '1');
}
string result;
for (int j = 0; j<n; ++j){
int fac =factorial(n-j-1);
int idx = k/fac;
k = k%fac;
result += str[idx];
str.erase(str.begin()+idx);
}
return result;
}
private:
int factorial(int n){
int fac = 1;
for (int i = 1; i<=n; ++i){
fac *= i;
}
return fac;
}
};
```