46. 全排列

[Geekhyt]

原题链接

回溯法

题目要求我们返回所有可能的全排列，我们就要考虑到所有的情况，可以使用回溯法解题。

回溯法的本质是枚举，并且还可以通过剪枝少走一些冤枉路。

回溯：一条路走到黑，手握后悔药，可以无数次重来。(英雄联盟艾克大招无冷却)。

关键点：在递归之前做选择，在递归之后撤销选择。

1. 借助 deepStack 栈暂存每一种枚举的可能情况。
2. 开启遍历枚举，已经选择过的数字不能再做选择。
3. 在递归之前做选择，在递归之后需要撤销选择，恢复状态。
4. 完成所有遍历时，将 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!)