# [recommend for beginners]clean C++ implementation with detailed explanation

• ``````class Solution {
public:
string getPermutation(int n, int k) {
int i, j, base=1;
string s(n, '0');
for(int i=1; i<=n; i++){
base*=i;
s[i-1]+=i; /*** change string s to "12345..." ***/
}
/***
* n=4 k=10  n!=24
* i=0 base=6 k=10  s=[2,1,3,4]
* i=1 base=2 k=4   s=[2,3,1,4]
* i=2 base=1 k=0   s=[2,3,4,1]
***/
for(i=0, k--; i<n; i++){
base/=(n-i); /*** f/(n-i) is the i-th base ***/
j=i+k/base; /*** f/base is the i-th value-index ***/
char c=s[j];
/*** move the remained number tegother **/
while(j>i)  { s[j]=s[j-1]; j--;}
k%=base;
s[i]=c;
}
return s;
}
};``````

• Can you explain in more detail the reasoning behind the implementation and the reasoning for each step?

• @benjie

You can think that for the number start with "1", the rest position have n-1 number, so there are (n-1)! combinations , So we can devide the k by (n-1)! to check the number in the left-most-pos. Similarly .... You get the final result .

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