46-全排列.md

46. 全排列

leecode原题

题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例

示例 1:

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3:

输入：nums = [1]
输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

解题思路

思路

以[1,2,3]为例，抽象成树形结构如下:

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出叶子节点，就是收割结果的地方。那么什么时候，算是到达叶子节点呢？当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

此时可以感受出排列问题的不同：

• 每层都是从0开始搜索而不是startIndex
• 需要used数组记录path里都放了哪些元素了

实现

源码

var (
	res  = make([][]int, 0) // 存放最终结果
	path = make([]int, 0)   // 存放中间结果集
	used = make([]int, 0)   // 存放数值是否被使用
)

func backtracking(nums []int) {
	// 此时说明找到了一组
	if len(path) == len(nums) {
		temp := make([]int, len(path))
		copy(temp, path)
		res = append(res, temp)
		return
	}
	// 注意每次i都从0开始
	for i := 0; i < len(nums); i++ {
		if used[i] == 1 {
			continue
		}
		path = append(path, nums[i])
		used[i] = 1
		backtracking(nums)
		used[i] = 0
		path = path[:len(path)-1]
	}
}

func permute(nums []int) [][]int {
	res = make([][]int, 0)        // 存放最终结果
	path = make([]int, 0)         // 存放中间结果集
	used = make([]int, len(nums)) // 存放数值是否被使用
	backtracking(nums)
	return res
}