LeetCode Q60: 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.

    I didn't end up with this solution myself again, sigh... But, my idea is almost there as similar as the code I show below. The idea is not to do the swapping or insertion to the string. Instead, we can directly "compute" the string by looking at how many permutations are available for each given number n. Say, if n=4, and in total it will give 24 permutations, and we are going to pick the k=10 string. To decide which number we should use for the most significant bit, we should look at how many permutations are there for digits that are after the most significant digit. In this example, there 3 digits after the most significant one, and with 3 digits, there will be 6 possible permutations. So, we know the significant digit can not be 1, because there are only 6 possible string in form of 1XXX. Thus, the most signification digit has to be 2, because, 2XXX has another groups of 6 permutations which must contain our target one.

    So on so forth,  we can compute the digit from significant digit to least significant digit.