[leetcode] Permutation Sequence

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 kth permutation sequence.

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

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

```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;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.