46. 全排列
文章目录
- [46. 全排列](https://leetcode.cn/problems/permutations/)
- - 递归枚举
- - 回溯法
- 结语
给定一个不含重复数字的数组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]]思路
- 这道题主要考察的是递归，但是这道题递归的思路分为两种，一种是递归枚举，一种是回溯，二者的差异主要在于对于已经排列的数字的状态管理方式不一样，下面分别来解析不同方法的思路，可以很轻松的理解状态管理的差异在什么地方
- 递归枚举
传参：
- 结果集（二维数组，用来把结果保存下来）
- 已排序的数字组合（一维数组）
- 原数组（所有需要排序的数字）
- 新增排列数（用下标管理，每次进入递归函数都在已排序的数字组合后面加一个数）
funcpermute(nums[]int)[][]int{//结果集，用来记录结果ret:=[][]int{}dfs(&ret,[]int{},nums,-1)returnret}funcdfs(ret*[][]int,cur[]int,nums[]int,indexint){//将cur当前排列好的数字拷贝过来，否则会重复操作同一块数据temp:=append([]int{},cur...)//第一次调用dfs的时候没有要排序的数字，所以index传参-1ifindex!=-1{//将当前新排列的数字追加在后面temp=append(temp,nums[index])}//如果已排列数字的长度等于原数组长度，说明全部排列好了iflen(temp)==len(nums){//把结果写入结果集*ret=append(*ret,temp)return}//如果还没有排列好，就把已排列的数据记录一下，待会直接把未排列的数字传入dfs()即可flag:=map[int]bool{}for_,v:=rangetemp{flag[v]=true}//遍历nums，去flag里面找出所有未排列的数字，传入dfs追加排列fori,v:=rangenums{if!flag[v]{dfs(ret,temp,nums,i)}}}大家一定发现了，上面的方法在状态管理做的很不好，因为每次递归都需要重新分配一块空间用来记录数字是否被使用过，所以我们要使用回溯，当一个组合被写入结果集之后，把所有此前的标记撤离，继续使用同一块空间来记录数字是否被使用过
- 回溯法
这里我们使用闭包的方式，不需要传参
使用到的参数有
- ans用来记录结果集
- path当前排列的数字
- used使用过的数字
funcpermute(nums[]int)[][]int{ans:=make([][]int,0)path:=make([]int,0)//当前排列是什么样子used:=make([]bool,len(nums))//初始化一下 并且全部为falsevardfsfunc()dfs=func(){iflen(path)==len(nums){tmp:=append([]int(nil),path...)ans=append(ans,tmp)return}//如果还不满足fori:=0;i<len(nums);i++{ifused[i]{continue}//否则这个还没有被选used[i]=truepath=append(path,nums[i])dfs()//回溯一下used[i]=falsepath=path[:len(path)-1]}}dfs()returnans}
结语
本文是 《算法题目解析系列》 的第 [33] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。欢迎关注，第一时间获取更新。如果你有想看的题目，也可以在评论区留言告诉我。
