DFS + Perm Pruning with Counting/Maths
(credits to chatgpt for formatting the editorial :p, me sorry if it messed up a little)IntuitionThe problem requires finding the K-th lexicographically smallest
(credits to chatgpt for formatting the editorial :p, me sorry if it messed up a little)


<h2><strong>Intuition</strong></h2>
<p>The problem requires finding the K-th lexicographically smallest alternating permutation of the first n natural numbers. Instead of generating all permutations, we can leverage factorial counting and DFS pruning to efficiently construct the answer.</p>

<h2><strong>Key Observations:</strong></h2>
<ol>
    <li><strong>Alternating condition:</strong> Adjacent numbers must have different parity (odd/even).</li>
    <li><strong>Total valid permutations:</strong>
        <ul>
            <li>If <em>n</em> is odd: odd -> even -> odd .... -> odd:</li>
            <pre>fact(oddNum) × fact(evenNum)</pre>
            <li>If <em>n</em> is even: odd -> even -> ... -> even or even -> odd .... -> odd, 2 possibilities, so:</li>
            <pre>2 × fact(oddNum) × fact(evenNum)</pre>
        </ul>
    </li>
    <li>At position <em>i</em>, the remaining valid permutations if it is already decided which parity is to be placed here (even or odd):</li>
    <pre>fact(oddNumLeft) × fact(evenNumLeft)</pre>
</ol>

<h2><strong>Approach</strong></h2>
<ol>
    <li><strong>Precompute Factorials:</strong>
        <ul>
            <li>To efficiently determine the number of valid permutations from any position, precompute factorials up to a reasonable limit (e.g., 20!) since values beyond this will overflow.</li>
            <li>Store factorials in an array <code>fact[]</code> where <code>fact[i] = i * fact[i - 1]</code>.</li>
        </ul>
    </li>
    <li><strong>Use DFS with Counting and Pruning:</strong>
        <ul>
            <li>Maintain two sets of numbers: <strong>odd numbers</strong> and <strong>even numbers</strong>.</li>
            <li>At each position <em>i</em>, decide whether to place an odd or even number based on the alternating pattern.</li>
            <li>Always try to place number going from the smallest available number (with the matching parity of position) to the larger ones on the position <em>i</em> to ensure <em>k</em>th permutation in lexicographical order.</li>
        </ul>
    </li>
    <li><strong>Count Remaining Valid Permutations:</strong>
        <ul>
            <li>For a given number placement, compute how many permutations are possible with the remaining numbers.</li>
            <li>If <em>n - i</em> numbers are left, the count of permutations is:
                <pre>fact((n - i) / 2) × fact((n - i + 1) / 2)</pre>
            </li>
            <li>This tells us how many sequences exist starting from the current number.</li>
        </ul>
    </li>
    <li><strong>Prune Unnecessary Branches:</strong>
        <ul>
            <li>Compare <code>k</code> with the computed count of permutations for a branch.</li>
            <li>If <code>k</code> is greater than the count of permutations in the current branch, it means the answer does not exist in this branch.</li>
            <li>In this case, <code>k</code> is decremented accordingly, and we move to the next possible number.</li>
            <li>Otherwise, we place the current number and recurse further.</li>
        </ul>
    </li>
    <li><strong>Use a Boolean Array to Track Used Numbers:</strong>
        <ul>
            <li>Maintain an array to mark whether a number has been used.</li>
            <li>This prevents duplicate placements and ensures we follow the alternating pattern correctly.</li>
        </ul>
    </li>
    <li><strong>Construct the Answer Recursively:</strong>
        <ul>
            <li>Continue this process until all positions are filled.</li>
            <li>The recursion builds the answer step by step without generating all permutations explicitly.</li>
        </ul>
    </li>
</ol>

# Complexity
- Time complexity: O(N^2)
- Space complexity: O(N^2)

# Code
```cpp []
vector<long long> fact(101, LLONG_MAX);

void init(){
    if(fact[0] == 1) return;
    fact[0] = 1;
    for(int i = 1; i <= 20; i++)
        fact[i] = i * fact[i - 1];
}

class Solution {
public:
    int n, numsLeft[2];
    vector<int> ans;
    
    long long calcPerms(int odd, int even){
        long long fromOdd = fact[odd];
        long long fromEven = fact[even];

        long long totalPerms = LLONG_MAX;
        if(log10(fromOdd) + log10(fromEven) <= 18)
            totalPerms = fromOdd * fromEven;
        
        return totalPerms;
    }
    //placeOdd == -1, can place anything here, (haven't started)
    void constructArray(int placeOdd, array<vector<bool>, 2> &numsChosen, long long k){
        if(numsLeft[0] + numsLeft[1] == 0)
            return;
        
        long long nextPerms;
        if(placeOdd == -1) nextPerms = calcPerms(numsLeft[1], numsLeft[0] - 1);
        else nextPerms = calcPerms(numsLeft[1] - placeOdd, numsLeft[0] - !placeOdd);

        for(int i = 1; i <= n; i++){
            if(placeOdd == -1 || ((i & 1) == placeOdd)){
                if(!numsChosen[i & 1][i]){
                    if(k > nextPerms) k -= nextPerms;
                    else{
                        numsLeft[i & 1]--;
                        ans.push_back(i);
                        numsChosen[i & 1][i] = 1;
                        constructArray(!(i & 1), numsChosen, k);
                        break;
                    }
                }
            }
        }
    }
    vector<int> permute(int n, long long k) {
        init();
        this -> n = n;
        numsLeft[1] = (n + 1) / 2, numsLeft[0] = n / 2;
        
        array<vector<bool>, 2> numsChosen = {vector<bool> (n + 1, false), vector<bool> (n + 1, false)};
        // if evenDigits, can start from both odd or even
        int placeOdd = n % 2 ? 1 : -1;
        constructArray(placeOdd, numsChosen, k);
        
        return ans;
    }
};
```


(BTW There was a similar question in Meta Hackercup R1 last year)
['Depth-First Search', 'C++']