- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
回溯法
题目要求我们返回所有可能的全排列，我们就要考虑到所有的情况，可以使用回溯法解题。
回溯法的本质是枚举，并且还可以通过剪枝少走一些冤枉路。
回溯：一条路走到黑，手握后悔药，可以无数次重来。(英雄联盟艾克大招无冷却)。
关键点：在递归之前做选择，在递归之后撤销选择。
- 借助 deepStack 栈暂存每一种枚举的可能情况。
- 开启遍历枚举，已经选择过的数字不能再做选择。
- 在递归之前做选择，在递归之后需要撤销选择，恢复状态。
- 完成所有遍历时，将 deepStack 存入结果集 res。
constpermute=function(nums){constlen=nums.length,res=[],deepStack=[]constbacktrack=(deepStack)=>{// 递归终止条件if(deepStack.length==len){returnres.push(deepStack)}for(leti=0;i<len;i++){// 已经选择过的数字不能再做选择if(!deepStack.includes(nums[i])){deepStack.push(nums[i])// 做选择backtrack(deepStack.slice())deepStack.pop()// 撤销选择}}}backtrack(deepStack)returnres}
- 时间复杂度: O(n * n!)
- 空间复杂度: O(n * n!)