Permutations IV
Complexity
Time complexity: O(N^2)

Space complexity: O(N)
Code


# 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)$$ -->

# Code
```python []
class Solution(object):
    def permute(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[int]
        """
        result = []
        cnt = [1]*n
        for i in xrange(len(cnt)-1):
            cnt[i+1] = min(cnt[i]*((i+2)//2), k)
        lookup = [False]*n
        for i in xrange(n):
            for j in xrange(n):
                if not (not lookup[j] and ((i == 0 and n%2 == 0) or (j+1)%2 == (1 if not result else (result[-1]%2)^1))):
                    continue
                if k <= cnt[n-1-i]:
                    break
                k -= cnt[n-1-i]
            else:
                return []
            lookup[j] = True
            result.append(j+1)
        return result
```
['Array', 'Math', 'Combinatorics', 'Python']