0060. Permutation Sequence

# 60. 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 kth 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"

``````

## 解题思路 #

• 用 DFS 暴力枚举，这种做法时间复杂度特别高，想想更优的解法。

## 代码 #

``````
package leetcode

import (
"fmt"
"strconv"
)

func getPermutation(n int, k int) string {
if k == 0 {
return ""
}
used, p, res := make([]bool, n), []int{}, ""
findPermutation(n, 0, &k, p, &res, &used)
return res
}

func findPermutation(n, index int, k *int, p []int, res *string, used *[]bool) {
fmt.Printf("n = %v index = %v k = %v p = %v res = %v user = %v\n", n, index, *k, p, *res, *used)
if index == n {
*k--
if *k == 0 {
for _, v := range p {
*res += strconv.Itoa(v + 1)
}
}
return
}
for i := 0; i < n; i++ {
if !(*used)[i] {
(*used)[i] = true
p = append(p, i)
findPermutation(n, index+1, k, p, res, used)
p = p[:len(p)-1]
(*used)[i] = false
}
}
return
}

``````

Sep 6, 2020