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 (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

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

Note: Given n will be between 1 and 9 inclusive.

tag里说可以用回溯。我直接用了递归。o(n)的复杂度。

每次层递归时通过一个除法确定第一个字符，通过一个取余确定接下来字符串确定的index。

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<char> elements;
        for(int i = 1; i <= n; i++){
            elements.push_back(i + '0');
        }
        return _getPermutations(elements, k - 1);
    }
    string _getPermutations(vector<char> elements, int k){
        
        int size = elements.size();
        if(size == 1){//base condition
            return string(1, elements[0]);
        }
        int factorial = 1;
        for(int i = 1; i < size; i++){
            factorial *= i;
        }
        int reminder = k % factorial;
        int q = k / factorial;
        char c = elements[q];
        elements.erase(elements.begin() + q);
        string re = _getPermutations(elements, reminder);
        re.insert(re.begin(), c);
        return re;
    }
};