O(N^2) | Count Tail Combinations
IntuitionPermutations should be alternating which means we need to change parity of the picked value for every next position.The first thing that came to my min
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

Permutations should be alternating which means we need to change parity of the picked value for every next position.

The first thing that came to my mind was splitting all source number into 2 sets - `odd` and `even`, and then try to fill every result position from left to right. To choose the proper value for a position we can try every available number in ascending order and estimate how many tail combinations exist for thi number. Once we get a number which "tail" combinations exceed K we pick that number and proceed to the next position. A simle analogy could be a virtial tree in which we know the number of chilren for every intermediate node. The children would be complete combintations of length `N` while intermetiate node - prefixes of those final combination.

Also, there are several tricky places we need to address:
- the number of suffixes can be huge - up to `100! ~= 10 ^ 157`, we don't want to overflow errors or slow calculations in case of Python here
- we will use repeated factorial values a lot, it can be a good idea to have all of then pre-computed or cached
- make sure you don't count incorrect combination, like 2 even and 0 odd numbers, which may appear in the `N = 3` test case for example

# Approach
<!-- Describe your approach to solving the problem. -->

1. Build the list of all available numbers - `nums`. Split it into 2 sets: `odd` and `even`.
2. Define a `max_k` variable which is greater than `K` and will be used whenever we meet an overflowing number of tail combinations.
3. Reduce `K` by 1 to switch to 0-based numbering.
4. Define an array / cached function with the factorial values for range `[0, N]` (if you don't have a proper library function or don't trust / know it well eough). Use `max_k` here to replace overflowing factorial values.
5. Define a function to count possible way to combine `L` odd and `M` even numbers into an alternating suffix. Specify which number goes first - `count_combos`.
    1.  Make sure there are enough values in both "bins" to get a valid alternating sequence. E.g. 2 odd number and 0 even can't be used to create an alternative sequence.
    1.  The number of combintations is: `odd! * even!`.
    1.  Handle overflowing results here as well. (`max_k` should come in handy)
    1. You may consider simplifying the function by keeping only `set1, set2` parameters and always starting with the numbers from the first set. Then you should call it with appropriate `odd`/`even` parameters order.
7. Create a result array of size `N` and for every its position do the following:
    1. Define a `skipped` variable to keep track of "tails" / suffixes we skip. (It's possible to get rid of this variable and decrease `k` for every prefix right when we skip a candidate.)
    1. Define a flag to identify whether we've found a value for the currect position of not - `picked`.
    1. Try every possible candidate value in ascending order
        1. Get the parity of the candidate value.
        2. Make sure it's not equal to the previous value's parity.
        3. Compute the number of tail combinations we can get by choosing the current candidate: call `count_combos` with the number of leftover odd and even numbers.
        4. Check the target `K`-th permutation lies within the `[skipped, skipped + K)` range.
            5. If it does - we've found the right number for the current position: remove the number from all candidate collections, set the `picked` flag, decrease `K` by the number of permutation we've met before the current candiudate (`skipped`) and break the candidates loop.
            6. Otherwise we haven't reached teh the `k`-th permutation and need to proceed to the next candidate. Update the number of seen permutations here - `skipped`.
    2. If no value has been picked for the current position, return empty array. (Note: don't actaully need a separate flag here, `idx` and `len(result)` can tell us if we miss the value.)
1. Return the computed permutation - `result`.

# Complexity
- Time complexity: $$O(N^2)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(N)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

`N` is the total number of values we try to permute.

# Code
```python3 []
def permute(self, n: int, k: int) -> List[int]:
    nums = list(range(1, n + 1))
    odd = set([v for v in nums if v % 2 == 1])
    even = set([v for v in nums if v % 2 != 1])

    max_k = k * 10
    k -= 1              # 0-based

    @cache
    def fact(n):
        if n <= 1:
            return 1
        return min(n * fact(n-1), max_k)

    def count_combos(odd, even, odd_start):
        if odd_start and (odd < even or odd > even + 1):
            return 0
        if not odd_start and (even < odd or even > odd + 1):
            return 0
        return min(fact(odd) * fact(even), max_k)
    
    result = []
    for idx in range(n):
        skipped = 0
        picked = None
        for val in nums.copy():
            is_odd = val % 2 == 1
            if result and is_odd == result[-1] % 2:
                continue
            tails = count_combos(len(odd) - is_odd, len(even) - (1 - is_odd), not is_odd)
            if skipped + tails > k:
                # found the right value withing [skipped, skipped + tails)
                result.append(val)
                nums.remove(val)
                if is_odd:
                    odd.remove(val)
                else:
                    even.remove(val)
                k -= skipped
                picked = True
                break
            else:
                skipped += tails
        if picked == None:
            return []
    return result
```
['Tree', 'Combinatorics', 'Counting', 'Python3']