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