Kth Permutation Sequence

• Time : $O(n^2)$
• Space : $O(n)$

int fact(int n, int k) {
    int res = 1;
    for(int i = 1; i <= n and res <= k; i++) res *= i;
    return res;
}
string helper(set<int>& s, int k) {
    if(s.size() == 1) return to_string(*begin(s));
    else {
        int perm = s.size() - 1;
        int fac = fact(perm,k);
        int jump = k / fac;
        int num = *next(s.begin(), jump);
        s.erase(num);
        return to_string(num) + helper(s,k-jump * fac);
    }
}
string Solution::getPermutation(int A, int B) {
    set<int> s;
    for(int i = 1; i <= A; i++) s.insert(i);
    return helper(s,B-1);
}