# Sharing my straightforward C++ solution with explanation

• ``````string getPermutation(int n, int k) {
int pTable[10] = {1};
for(int i = 1; i <= 9; i++){
pTable[i] = i * pTable[i - 1];
}
string result;
vector<char> numSet;
numSet.push_back('1');
numSet.push_back('2');
numSet.push_back('3');
numSet.push_back('4');
numSet.push_back('5');
numSet.push_back('6');
numSet.push_back('7');
numSet.push_back('8');
numSet.push_back('9');
while(n > 0){
int temp = (k - 1) / pTable[n - 1];
result += numSet[temp];
numSet.erase(numSet.begin() + temp);
k = k - temp * pTable[n - 1];
n--;
}
return result;
}
``````

In this program, `pTable` refers to permutation table and `numSet` refers to a set of numbers from 1 to 9. Before while loop, we need to initialize `pTable` and `numSet`, which is trivial.

In while loop, we do these following things.

1 calculate which number we will use.

2 remove that number from `numSet`.

3 recalculate k.

4 `n--`.

Finally, we return result.

• This is an amazing solution! How do you come up with this one ? Mine is not that elegant.

• For this problem, you can start with several simple examples, like 123 and 1234. It's easier to find a pattern from them. Then think about general situation. Good luck :)

• No problem :)

• I would like to make the code more concise for your reference.

First, the pTable array is redundant. We could just use a int value, like `factorial`, and recalculating it in the loop by `factorial /= n;`. While its ok to use pTable because `n` is no more than `9`.

Second, I think sentence `vector<char> numSet;` can be modified to `vector<int> numSet`, thus we could initialize it using:

``````for (int idx = 1; idx <=n; ++idx) {
numSet.push_back(idx);
}
``````

here, `result += numSet[temp];` can be `result += '0' + numSet[temp];`

Then, the way recalculating the k makes me confused at first sight. I think it can be more clear by using `k %= pTable[n - 1];` which means the remain permutations.

Thx.

• I think your algorithm is O(n^2), not O(n). Because each time you call vector<T>::erase(it), the time complexity is O(n), and you call it n times. So your time complexity is O(n^2).

• This post is deleted!

• it's not necessary to use push_back() to initialize the numSet. In C++11, which is supported by LeetCode, there's an easy way like this :
`vector<char> numSet{'1', '2', '3', '4', '5', '6', '7', '8', '9'};`

• Very nice solution!

Just want to make it a bit more concise.

Also, handle the case if k > n!

``````class Solution {
public:
string getPermutation(int n, int k) {
int pTable[10] = {1};        //factorial pre-calculated
for(int i = 1; i < 10; i++)  pTable[i] = i * pTable[i-1];

vector<char> numSet;         //in-order num set to fetch numbers
for(int i = 0; i < n; i++) numSet.push_back('0'+i+1);

string ans = "";
int k1 = (k-1) % pTable[n];  //if k > n!. (k-1) for zero-based index
int n1 = n;

while(n1 > 0) {
int numPermutation = k1 / pTable[n1-1];
ans += numSet[numPermutation];
numSet.erase(numSet.begin()+numPermutation);
k1 %= pTable[n1-1];
n1--;
}
return ans;
}
}``````

• We don't always need 9 digits, get `n` digits for `numSet`.
And, save some space of `pTable`.

``````class Solution {
public:
string getPermutation(int n, int k) {
int pTable = n, temp;
vector<char> numSet(n, '1');
for(int i = 1; i < n; i++){
pTable *= i;
numSet[i] = numSet[i-1] + 1;
}
string res;
while( n > 0 ){
pTable /= n;
temp = (k-1)/pTable;
res += numSet[temp];
numSet.erase(numSet.begin() + temp);
k -= temp * pTable;
n--;
}
return res;
}
};
``````

• A version based off of @zxyperfect :

``````string getPermutation(int n, int k)
{
const int fact[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };

char seq[] = "123456789";
char res[] = "000000000";

for (int i = 1; i <= n; ++i)
{
// find index and copy the corresponding digit to the result
auto idx = (k - 1) / fact[n - i];
res[i - 1] = seq[idx];

// erase seq[idx] by writing over it
for (int j = idx; j < n; ++j)
seq[j] = seq[j + 1];

// reduce k
k -= idx * fact[n - i];
}

return string(res, res + n);
}
``````

• The erase() function of vector will always create a new vector array and copy the original value to it except the erased one. So the time complexity is O(n^2).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.