全排列

题目描述

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

解题思路

使用回溯算法（DFS + 回溯）。核心是经典的回溯三步走模式：

1. 路径（path）：记录当前已选择的数字。
2. 选择列表：used[] 数组标记每个数字是否已被使用。
3. 终止条件：path.length === nums.length 时，将当前路径加入结果。

递归流程：

• 遍历 nums，跳过已使用（used[i] === true）的数字。
• 将当前数字加入路径，标记为已使用，递归进入下一层。
• 递归返回后撤销选择（path.pop() + used[i] = false），这就是回溯。

代码实现

/**
 * 全排列 — 回溯法
 * @param {number[]} nums - 不含重复数字的数组
 * @returns {number[][]} 所有可能的全排列
 */
function permute(nums) {
    if (!nums.length) return [];
    const result = [];
    const used = new Array(nums.length).fill(false);
    const path = [];

    const dfs = () => {
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.push(nums[i]);
            used[i] = true;
            dfs();
            used[i] = false;  // 回溯：撤销标记
            path.pop();        // 回溯：撤销选择
        }
    };

    dfs();
    return result;
}

复杂度分析

• 时间复杂度：O(n × n!)，其中 n! 是排列总数，每次复制 path 需要 O(n)。
• 空间复杂度：O(n)，递归栈深度为 n，used 和 path 数组各占 O(n)。

nums = [1, 2, 3]

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]