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{//将当前新排列的数字追加在后面tempappend(temp,nums[index])}//如果已排列数字的长度等于原数组长度说明全部排列好了iflen(temp)len(nums){//把结果写入结果集*retappend(*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()dfsfunc(){iflen(path)len(nums){tmp:append([]int(nil),path...)ansappend(ans,tmp)return}//如果还不满足fori:0;ilen(nums);i{ifused[i]{continue}//否则这个还没有被选used[i]truepathappend(path,nums[i])dfs()//回溯一下used[i]falsepathpath[:len(path)-1]}}dfs()returnans}结语本文是 《算法题目解析系列》 的第 [33] 篇本系列将持续更新每篇都提供清晰的思路与编程语言实现。欢迎关注第一时间获取更新。如果你有想看的题目也可以在评论区留言告诉我。