1
class Solution {
2
 public:
3
  string getPermutation(int n, int k) {
4
    int fact = 1;
5
    vector<int> numbers;
6
    for (int i = 1; i < n; i++) {
7
      fact = fact * i;
8
      numbers.push_back(i);
9
    }
10
    numbers.push_back(n);
11
    string ans = "";
12
    k = k - 1;
13
    while (true) {
14
      ans = ans + to_string(numbers[k / fact]);
15
      numbers.erase(numbers.begin() + (k / fact));
16
      if (numbers.size() == 0) break;
17
      k = k % fact;
18
      fact = fact / numbers.size();
19
    }
20
    return ans;
21
  }
22
};