LeetCode 60 排列序列

题目链接：

https://leetcode.cn/problems/permutation-sequence/

以下是使用Go语言实现外观数列问题的代码：

func getPermutation(n int, k int) string {
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		nums[i] = i + 1
	}
	var res string
	backtrack(nums, k, &res)
	return res
}

func backtrack(nums []int, k int, res *string) {
	if k == 0 {
		return
	}
	if len(nums) == 1 {
		*res += strconv.Itoa(nums[0])
		k--
		return
	}
	cnt := factorial(len(nums) - 1)
	idx := (k - 1) / cnt
	*res += strconv.Itoa(nums[idx])
	k -= idx * cnt
	nums = append(nums[:idx], nums[idx+1:]...)
	backtrack(nums, k, res)
}

func factorial(n int) int {
	res := 1
	for i := 2; i <= n; i++ {
		res *= i
	}
	return res
}

算法思路：

这是一道数学题。首先我们知道，对于n个数字的排列，其总共的排列数为n!个，可以将其想象成一个n叉树，每一层代表当前数字的位置，每个节点代表一个数字的选择，比如第一层，可以选择1,2,3中的任意一个数字，选择了一个数字之后，下一层只能从未被选择的数字中再选一个，以此类推，一直到选择完n个数字为止。

从根节点到叶子节点的每一条路径就代表了一种排列，比如213这个排列，对应的就是从根节点到3->1->2这条路径。

如果要求第k个排列，我们可以使用回溯算法来遍历这棵树，每次遍历到叶子节点的时候就将计数器+1，当计数器等于k时，就找到了第k个排列。

注意：根据题目要求，排列按照字典序升序排列，因此需要将每个节点的子节点按照升序排列，这样才能保证遍历到的每个排列都是按照字典序排列的。

时间复杂度：O(n^2)，其中n是给定的整数，计算阶乘的时间复杂度为O(n)，回溯的时间复杂度为O(n)，因为n最大为9，所以可以认为时间复杂度为O(1)。

空间复杂度：O(n)，其中n是给定的整数，空间复杂度主要取决于回溯时使用的辅助数组。