📑 题目：60. 排列序列

🚀 本题 LeetCode 传送门

题目大意

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：“123”，“132”，“213”，“231”，“312”，“321”，给定 n 和 k，返回第 k 个排列。

解题思路

• 用 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, 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
}