Easy Pattern Based C++ | DFS + Greedy | Just Tricky Handling Large Number
IntuitionIt's a general pattern question where you ignore smaller ranges by precomputing the possible count of patterns if a number is placed in the current pos
# **Intuition**  
It's a general pattern question where you ignore smaller ranges by precomputing the possible count of patterns if a number is placed in the current position.  

- If count is **less than \( K \)**, we subtract that count from \( K \) and move to the next valid number (choosing the **lexicographically smallest** option).  
- If count is **greater than \( K \)**, we keep that number in the answer and go further in depth, repeating the process.  

### **Key Insight**  
- If \( n \) is **even**, we have equal odd and even numbers. So in the answer array, we can start with **odd or even** and then alternate.  
- If \( n \) is **odd**, we **must start with an odd number**; otherwise, a **last odd-odd conflict** will arise.  

---

# **Approach**  

![image.png](https://assets.leetcode.com/users/images/58338df9-7956-4ede-954e-184cf23600d0_1741341279.5791612.png)  

![image.png](https://assets.leetcode.com/users/images/46619929-9ecb-47fe-ba24-940400ceb1d7_1741341318.5255644.png)  

![image.png](https://assets.leetcode.com/users/images/11ca79f6-b64a-4c6b-b593-73f2f431c6d0_1741341341.9088235.png)  

### **Handling Constraints Efficiently**  
The main issue here was **constraints**:  
- Since \( n = 100 \), we need at most \( 50! \), but **this is useless** since it exceeds \( K \).  
- We use **safe multiplication** or **logarithms** instead.  
- Both approaches are provided in the code.  

### **Key Steps in the `permute` Function**  
- We **first check** if the \( K \)-th permutation is possible.  
- If possible, we keep the **first element**; otherwise, we return `{}`.  

#### **Parity Constraints**  
- If \( n \) is **odd**, we can place **only odd numbers** in the first position.  
- Otherwise, we can place **any number** from \( 1 \) to \( n \).  

---

# **Doubts You Might Have**  

### **Why `esz - 1` in Factorial Calculation?**  
```cpp []
sum = safeMultiply(fact[(esz - 1)], fact[osz]);
```
Doubts you might have:
sum = safeMultiply(fact[(esz - 1)], fact[osz]);  
(esz - 1) => evenSize -1. meaning example {2,4,6}
if 2 is place then set has 2 elements so esz-1.
but is count was less than K after place we move to 4.
now you might think esz-2 but no, since we are place 4 in place of 2 so set still has {2,6} because we din't place them yet so again esz-1.


# Complexity
- Time complexity: $$O(N²)$$
- Space complexity:$$O(N)$$

# Code
```cpp [C++ code using log]
class Solution {
public:
    typedef long long int ll;
    vector<long double> fact;
    
    Solution() : fact(51, 1.0L) {}

    void precompute() {
        fact[0] = 1.0L;
        for (int i = 1; i <= 50; i++) {
            fact[i] = fact[i - 1] * i;
        }
    }

    void solve(vector<int>& ans, set<int>& e, set<int>& o, long double k, int n) {
        if (ans.size() == n) return;

        if (ans.back() % 2 == 1) { 
            int p = e.size();
            int c = o.size();
            int i = 1;

            for (auto it = e.begin(); it != e.end(); ) {
                long double val = fact[p - i] * fact[c];
                if (val < k) {
                    k -= val;
                } else {
                    ans.push_back(*it);
                    it = e.erase(it);
                    solve(ans, e, o, k, n);
                    return;
                }
                ++it;
            }
        } else { 
            int p = o.size();
            int c = e.size();
            int i = 1;

            for (auto it = o.begin(); it != o.end(); ) {
                long double val = fact[p - i] * fact[c];
                if (val < k) {
                    k -= val;
                } else {
                    ans.push_back(*it);
                    it = o.erase(it);
                    solve(ans, e, o, k, n);
                    return;
                }
                ++it;
            }
        }
    }

    vector<int> permute(int n, ll k) {
        precompute();
        set<int> e, o;
        vector<int> ans;

        for (int i = 1; i <= n; i += 2) o.insert(i);
        for (int i = 2; i <= n; i += 2) e.insert(i);

        if (n % 2 == 1) {  
            if (log(fact[n / 2]) + log(fact[(n + 1) / 2]) < log(k)) return {};
            
            long double sum = 0;
            int osz = o.size();
            int esz = e.size();

            for (int i = 1; i <= n; i += 2) { 
                sum = fact[(osz - 1)] * fact[esz];

                if (sum >= k) {
                    ans.push_back(i);
                    o.erase(i); 
                    solve(ans, e, o, k, n);
                    return ans;
                }
                k -= sum;
            }
        } else {
            if (log(fact[n / 2]) + log(fact[n / 2]) + log(2) < log(k)) return {};
            
            long double sum = 0;
            int osz = o.size();
            int esz = e.size();

            for (int i = 1; i <= n; i++) { 
                if (i % 2 == 0)
                    sum = fact[(esz - 1)] * fact[osz];  
                else 
                    sum = fact[(osz - 1)] * fact[esz];

                if (sum >= k) {
                    ans.push_back(i);
                    if (i % 2 == 0) 
                        e.erase(i); 
                    else 
                        o.erase(i); 
                    solve(ans, e, o, k, n);
                    return ans;
                }
                k -= sum;
            }
        }

        return {};
    }
};

```
```cpp [C++ code using Safe Multiplication]
class Solution {
public:
    typedef long long int ll;
    vector<ll> fact;

    Solution() : fact(51, 1LL) {}

    void precompute() {
        fact[0] = 1LL;
        for (int i = 1; i <= 50; i++) {
            fact[i] = safeMultiply(fact[i - 1], (ll)i);
        }
    }

    ll safeMultiply(ll a, ll b) {
        if (a == 0 || b == 0) return 0;
        if (a > LLONG_MAX / b) return LLONG_MAX;  // Overflow check
        return a * b;
    }

    void solve(vector<int>& ans, set<int>& e, set<int>& o, ll k, int n) {
        if (ans.size() == n) return;

        if (ans.back() % 2 == 1) { 
            int p = e.size();
            int c = o.size();
            

            for (auto it = e.begin(); it != e.end(); ) {
                ll val = safeMultiply(fact[p - 1], fact[c]);
                if (val < k) {
                    k -= val;
                } else {
                    ans.push_back(*it);
                    it = e.erase(it);
                    solve(ans, e, o, k, n);
                    return;
                }
                ++it;
            }
        } else { 
            int p = o.size();
            int c = e.size();

            for (auto it = o.begin(); it != o.end(); ) {
                ll val = safeMultiply(fact[p - 1], fact[c]);
                if (val < k) {
                    k -= val;
                } else {
                    ans.push_back(*it);
                    it = o.erase(it);
                    solve(ans, e, o, k, n);
                    return;
                }
                ++it;
            }
        }
    }

    vector<int> permute(int n, ll k) {
        precompute();
        set<int> e, o;
        vector<int> ans;

        for (int i = 1; i <= n; i += 2) o.insert(i);
        for (int i = 2; i <= n; i += 2) e.insert(i);

        if (n % 2 == 1) {  
            if (safeMultiply(fact[n / 2], fact[(n + 1) / 2]) < k) return {};
            
            ll sum = 0;
            int osz = o.size();
            int esz = e.size();

            for (int i = 1; i <= n; i += 2) { 
                sum = safeMultiply(fact[(osz - 1)], fact[esz]);

                if (sum >= k) {
                    ans.push_back(i);
                    o.erase(i); 
                    solve(ans, e, o, k, n);
                    return ans;
                }
                k -= sum;
            }
        } else {
            if (safeMultiply(safeMultiply(fact[n / 2], fact[n / 2]), 2) < k) return {};
            
            ll sum = 0;
            int osz = o.size();
            int esz = e.size();

            for (int i = 1; i <= n; i++) { 
                if (i % 2 == 0)
                    sum = safeMultiply(fact[(esz - 1)], fact[osz]);  
                else 
                    sum = safeMultiply(fact[(osz - 1)], fact[esz]);

                if (sum >= k) {
                    ans.push_back(i);
                    if (i % 2 == 0) 
                        e.erase(i); 
                    else 
                        o.erase(i); 
                    solve(ans, e, o, k, n);
                    return ans;
                }
                k -= sum;
            }
        }

        return {};
    }
};

```


['C++']