46.全排列题目来源：https://leetcode-cn.com/problems/permutations/题目给定一个不重复的数字序列，返回所有可能的全排列。示例：输入：[1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]解题思路：深度优化搜索先看题目，以给定数组[1,2,3]的全排列为例：从1开始，完整排列为：[1,2,3],[1,3,2]；从2开始，完整排列为[2,1,3],[2,3,1]；从3开始，完整的排列是[3,1,2],[3,2,1]。从上面的情况可以看出。对每个数字列举出每一种可能的情况，所选的数字不能出现在后面的选择中。按照这种方法，将能够列出所有案例。这实际上是进行深度优先搜索，从根节点到叶子节点形成的路径是全排列。按照这个思路，还是按照上面的例子，以空列表[]开头，以1开头为例。现在确定它是从1开始的，那么列表就是[1]，现在选择[2]和[3]中的一个，先选2，最后一个只有数字3，这样就形成了完整的排列[1,2,3]。知道还有一种情况，就是[1,3,2]，那么如何实现从[1,2,3]到[1,3,2]的变化。深度优先搜索是如何实现的？其实从[1,2,3]返回到[1,2]的时候，取消数字3，因为当前层只能选择3，所以取消选择2，这样后面的程序就可以选择3啦以后也可以选2。代码实现类解决方案：defpermute(self,nums:List[int])->List[List[int]]:def_dfs(nums,depth,pmt,be_selected,length,ans):#表示深度优化的深度search等于数组长度时，说明此时已经生成全排列。#即已经选择了符合情况的选择。#将这个完整的排列添加到列表中。#这里需要注意的是pmt在参数传递中是按引用传递的，复制一份并添加到结果中ifdepth==length:ans.append(pmt[:])return#开始遍历foriinrange(length):#be_selected，表示元素在原数组中的状态，是否被选中，为True，No为Falseifnotbe_selected[i]:#当元素被选中时，改变状态be_selected[i]=True#将元素加入pmt，形成后续pmt.append(nums[i])#进入下一层遍历_dfs(nums,depth+1,pmt,be_selected,length,ans)#遍历结束，回溯,此时需要重新设置状态#上面说到`[1,2,3]`到`改成[1,3,2]`,undo3,然后undo2,重新选择#statechangebe_selected[i]=False#undopmt.pop()length=len(nums)iflength==0:return[]be_selected=[False]*lengthans=[]_dfs(nums,0,[],be_selected,length,ans)返回ans得到结果以上就是利用深度优化搜索的思想解决《46. 全排列》问题的主要内容。主要要注意的是状态重置。欢迎关注微信公众号《书所集录》
