46. 全排列

[swiftwind0405]

方法一：回溯法

解题思想：

• 用递归模拟出所有情况
• 遇到包含重复元素的情况，就回溯
• 收集所有到达递归终点的情况，并返回

代码：

var permute = function (nums) {
    const res = [];
    const backtrack = (path) => {
        // 3. 递归的终点
        if(path.length === nums.length) {
            res.push(path);
            return;
        }
        // 遍历所有数字
        nums.forEach(n => {
            // 2. 如果包含当前数字，也就是重复了，即死路，就不要递归了
            if (path.includes(n)) return;
            // 1. 把数字加到数组里，进行递归调用
            backtrack(path.concat(n));
        })
    };
    backtrack([]);
    return res;
};

复杂度分析：

• 时间复杂度：O(n!)：每次递归里都有一个for循环，但是每次for循环都会减1，所以时间复杂度就是n的阶层；
• 空间复杂度：O(n)：递归的本质是堆栈，所以空间复杂度是递归的深度，而递归的深度就是输入数组的长度。