0046.全排列

难度：🟡 中等

标签：数组、回溯

链接：46. 全排列

题目描述

给定一个不含重复数字的数组 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](./1.md)

解题思路

核心思想

本题要求解一个集合的所有排列组合，这是典型的组合搜索问题。解决这类问题的标准算法是 回溯法 (Backtracking)。回溯法本质上是一种深度优先搜索（DFS），通过探索所有可能的候选解，并在探索过程中动态地构建和撤销选择，来找到所有符合条件的解。

我们可以把解题过程想象成一个决策树：

• 树的每一层代表排列中的一个位置。

• 每一层的选择是在当前“可用”的数字中挑选一个。

• 从根节点到叶子节点的一条完整路径，就构成一个全排列。

思路选择

回溯法是解决此问题的最直接和最经典的思路。我们需要维护一个“路径”(path)来记录当前已经选择的数字，并通过递归来探索下一步的可能性。为了避免在一个排列中重复使用同一个数字，我们需要一个机制来判断某个数字是否已经被选择过。

关键步骤

1. 定义回溯函数：创建一个递归函数，例如 backtrack(choices, path, results)，其中 choices 是原始数组，path 是当前正在构建的排列，results 是最终的结果集。

2. 设置结束条件（Base Case）：当 path 的长度等于 choices 的长度时，说明我们已经构建了一个完整的排列。此时，应该将 path 的一个副本（非常重要，避免后续操作影响已存结果）添加到 results 中，并结束当前递归。

3. 遍历选择列表：在递归函数中，遍历原始数组 choices 中的每一个元素。

4. 做出选择与剪枝：

   • 对于每一个元素，检查它是否已经存在于当前的 path 中。如果存在，就跳过该元素（这就是“剪枝”操作，避免重复使用）。

   • 如果不存在，就将该元素添加到 path 的末尾（“做出选择”）。

5. 进入下一层决策：以更新后的 path 再次调用回溯函数，继续向更深层探索。

6. 撤销选择（Backtrack）：当深层递归返回后，需要将之前添加的元素从 path 中移除（“撤销选择”）。这一步至关重要，因为它使得程序能够返回上一层，并尝试其他的选择分支。

代码实现

/**
 * 回溯辅助函数
 * @param {number[]} choices - 原始选择列表 (nums)
 * @param {number[]} path - 当前已选择的路径
 * @param {number[][]} results - 最终结果集
 */
var backTracking = function (choices, path, results) {
    // 1. 设置结束条件：当路径长度等于选择列表长度，说明找到一个完整排列
    if (path.length === choices.length) {
        // 将路径的副本推入结果集
        results.push([...path]);
        return;
    }

    // 2. 遍历所有选择
    for (let i = 0; i < choices.length; i++) {
        // 3. 剪枝：如果路径中已包含该选择，则跳过
        if (path.includes(choices[i])) {
            continue;
        }

        // 4. 做出选择
        path.push(choices[i]);
        // 5. 进入下一层决策
        backTracking(choices, path, results);
        // 6. 撤销选择
        path.pop();
    }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    let results = [];
    backTracking(nums, [], results); // 启动回溯
    return results;
};

复杂度分析

• 时间复杂度：O(n × n!) 其中 n 是数组 nums 的长度。共有 n! 种排列方式。对于每一种排列，我们都需要 O(n) 的时间来将其复制到一个新的数组中并存入结果集。因此总时间复杂度为 O(n × n!)。

• 空间复杂度：O(n) 如果不考虑存储最终结果所需的空间，空间复杂度主要取决于递归的深度。递归栈的深度最多为 n，同时 path 数组也需要 O(n) 的空间。因此，空间复杂度为 O(n)。

相关题目

• 0047.全排列 II (包含重复数字的全排列)

• 0077.组合

• 0078.子集

总结

本题是学习回溯算法的入门必做题。其解法框架——“做出选择、递归探索、撤销选择”——是解决绝大多数组合、排列、子集、棋盘路径等问题的通用模板。深刻理解这个模板对于掌握递归和深度优先搜索至关重要。