## Description

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 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.
• Given k will be between 1 and n! inclusive.

Example 1:

``````Input: n = 3, k = 3
Output: "213"
``````

Example 2:

``````Input: n = 4, k = 9
Output: "2314"
``````

## Solution

1. `⌈9 / 3!⌉`: `2`
2. `⌈9-3!*(2-1) / 2!⌉`: `2`
3. `[9-3!*(2-1)-2!*(2-1) / 1!]`: `1`
4. `1`

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 `````` ``````func getPermutation(n int, k int) string { s := []rune{} total := 1 for i := 1; i <= n; i++ { total *= i s = append(s, rune(i)+rune('0')) } ret := make([]rune, n) idx := 0 for n > 0 { // (n-1)! total /= n // 当前层索引 i := (k - 1) / total // 移除 s[i] ret[idx] = s[i] s = append(s[:i], s[i+1:]...) // 减去前面组的数量，得到下一层的索引 k -= total * i idx++ n-- } return string(ret) } ``````