LeetCode "Permutation Sequence"

1A! This is actually a basic question in Combinatorics: if at digit[k] = n, it contributes (k-1)! * n to the targeted index.

class Solution {
public:
    unsigned long long nPrime(unsigned n)
    {
        if (n == 1) return 1;
        return n * nPrime(n - 1);
    }
    string getPermutation(int n, int k) {
        if (n == 1) return "1";
        unsigned long long nbase = nPrime(n - 1);
        k--;
        
        //    Record counts
        vector<int> inx;
        for (int i = n; i >= 1; i--)
        {
            int currInx = k / nbase;
            inx.push_back(currInx);

            k -= nbase * currInx;
            if(nbase > 1) nbase /= (i - 1);
        }

        //    Recover digits        
        string ret;
        unordered_set<int> mark;
        for (int i = 0; i < inx.size(); i++)
        {
            int currInx = inx[i];
            int k;
            for (k = 0; k < 9 && currInx >= 0; k ++)
            {
                if (mark.find(k) == mark.end()) currInx--;
            }
            ret += '0' + k;
            mark.insert(k - 1);
        }
        return ret;
    }
};