全排列

七崽爱吃小饼干2026/01/15阅读 1专栏算法合集

全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

codeType

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

codeType

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

codeType

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

解法

解法一

下面这种写法就是常规的dfs，但是存在大量的数组重新创建以及filter的过程，性能很差

function permute(nums: number[]): number[][] {
    const res: number[][] = [];
    const len = nums.length;
    
    const dfs = (path: number[], rest: number[]) => {
        if (path.length === len) {
            res.push(path);
            return;
        }
        rest.forEach(num => {
            dfs([...path, num], rest.filter(item => item !== num));
        });
    };
    dfs([], nums);
    return res;
};

解法二

下面这种写法主要是避免了重复创建数组，只有最后push答案时，才会浅拷贝创建数组。

这种写法直接在nums数组上进行交换，在回溯时再回复交换，从而不需要新建数组，也能确定接下来的走向。

function permute(nums: number[]): number[][] {
    const res: number[][] = [];
    const len = nums.length;

    // 递归函数：index表示【已确定区间】的末尾下标，[0, index) 是已确定的元素
    const backtrack = (index: number) => {
        // 递归终止：已确定区间覆盖整个数组，得到一个完整排列
        if (index === len) {
            // 这里要做浅拷贝：因为数组是原地修改的，防止后续交换影响结果
            res.push([...nums]);
            return;
        }
        // 待选区间：[index, len)，每个元素依次交换到index位置
        for (let i = index; i < len; i++) {
            [nums[index], nums[i]] = [nums[i], nums[index]]; // 交换，进入下一层
            backtrack(index + 1); // 递归，扩大已确定区间
            [nums[index], nums[i]] = [nums[i], nums[index]]; // 回溯，恢复原数组
        }
    };

    backtrack(0);
    return res;
};