60 Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence (i.e., for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the $$k^{th}$$ permutation sequence.

Solution

class Solution {
public:
    int factorial(int n) {
        if ( n == 0 ) return 1;
        else return factorial(n-1)*n;
    }
    string getPermutation(int n, int k) {
        string res;
        vector<int> nums;
        for ( int i = 1; i <= n; i++ ) nums.push_back(i);
        k = k-1;
        while ( n >= 1 ) {
            res += to_string(nums[k/factorial(n-1)]);
            nums.erase(nums.begin()+k/factorial(n-1));
            k = k%factorial(n-1);
            n -= 1;
        }
        return res;
    }
};