[c++] 4ms, memorize the count of permutations
IntuitionCreate a list to store the number of permutations below of n elements up to k ,then pick one by one.Approach

Generate the list and pop the last one
we
# Intuition
Create a list to store the number of permutations below of n elements up to k ,then pick one by one.

# Approach
1. Generate the list and pop the last one
we start from 
n = 0: [1]
and add corresponding permutation cout to the array
n = 1: [1,1] (1!)
n = 2: [1,1,1] (1! * 1!)
n = 3: [1,1,1,2] (2! * 1!)
n = 4: [1,1,1,2,4] (2! * 2!)
...(and so on)
(Because of k's limitation, this array won't be too long)
(The reason we need to pop the last one is because the last one means all the permutaion count (or something > k), which does not need)

2. Check the k is reachable
for even case, because all numbers can be the start point, so, if k > n * perm[n-1] (all allowed combination), which is not reachable.
for odd case, only odd number can be th start point, so the largest allowed permutation is (n+1)/2 * perm[n-1]
3. Generate list for store even/odd number
4. k have to -1
To convert k to the "order" of the permutation
5. Filling number to result
if n is longer than list, it is definitely start from odd 1
in this case, we start filling elements from both vectors until it needs to count permutation.
(In this case we need to carefully check which array is picked first when reaching the place that needs to count the permutation)

if n is odd, we pick 1 element base on the permutation from odd array and erase it, then switch to even array, until both array are empty.

if n is even, the process is almost the same, but the only difference is we need to carefully pick the element from the right array. (because the first element can be even)

(Since the largest n = 100, the cost of vector.erase() can be really small) 

# Complexity
- Time complexity:
O(n)

- Space complexity:
O(n)

# Code
```cpp []
class Solution {
public:
    vector<int> permute(int n, long long k) {
        //total perm: n = 2p: 2 * p!*p! n = 2p-1: p!*(p-1)!
        vector<long long> perm = {1};

        int i = 1;
        while (perm.back() <= k && perm.size() < n+1) {
            perm.push_back(perm.back() * ((i + 1) >> 1));
            i++;
        }

        perm.pop_back(); // total permutation from 1 to n-1, number n's selection is decided by n-1's permutaion

        if (n % 2 == 0 && k > perm.back() * n || n % 2 == 1 && k > perm.back() *(n+1)/2){
            return {};
        }

        vector<int> even;
        vector<int> odd;
        for (int i = 1; i <= (n >> 1); ++i){
            odd.push_back(2*i - 1);
            even.push_back(2*i);
        }
        if (n%2){
            odd.push_back(n);
        }
        k--;
        vector<int> res;
        if (n % 2 || n > perm.size()) {
            //n is odd
            //because if n > perm size, the start will always be 1
            bool start = true;
            for (i = n; i >= 1; --i) {
                if (i > perm.size()) {
                    if (start == true) {
                        res.push_back(odd[0]);
                        odd.erase(odd.begin());
                        start = false;
                    }
                    else {
                        res.push_back(even[0]);
                        even.erase(even.begin());
                        start = true;
                    }
                }
                else {
                    int q = k / perm[i - 1];
                    k %= perm[i - 1];
                    if (start == true) {
                        res.push_back(odd[q]);
                        odd.erase(odd.begin() + q);
                        start = false;
                    }
                    else {
                        res.push_back(even[q]);
                        even.erase(even.begin() + q);
                        start = true;
                    }
                }
            }
        }
        else {
            //the last combination is twice
            bool start;
            for (i = n; i >= 1; --i) {
                if (i == n) {
                    int q = k / perm[i - 1];
                    k %= perm[i - 1];
                    if (q % 2) {
                        //start from a even number
                        q >>= 1;
                        res.push_back(even[q]);
                        even.erase(even.begin() + q);
                        start = false;
                    }
                    else {
                        q >>= 1;
                        res.push_back(odd[q]);
                        odd.erase(odd.begin() + q);
                        start = true;
                    }
                }
                else {
                    int q = k / perm[i - 1];
                    k %= perm[i - 1];
                    if (start == false) {
                        res.push_back(odd[q]);
                        odd.erase(odd.begin() + q);
                        start = true;
                    }
                    else {
                        res.push_back(even[q]);
                        even.erase(even.begin() + q);
                        start = false;
                    }
                }
            }
        }
        return res;
    }
};
```
['Counting', 'C++']