46. 全排列 - Permutations

🎯 问题描述（来源于LeetCode）

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

说明：

所有整数互不相同。
每个排列是数组中所有元素的一种顺序排列。

示例：

示例 1：

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

示例 2：

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

💻 解题思路

思路：回溯法（DFS） + 标记数组

算法步骤

获取数组长度 n，初始化结果列表 ans、当前路径列表 path 和 selected 布尔数组（标记元素是否已被使用）。
定义递归函数 dfs(i)，其中 i 表示当前已选中的元素个数（即 path 的长度）：
- 如果 i == n，说明已选中所有元素，将 path 的副本加入 ans 并返回。
- 否则，遍历每个元素的下标 j：
  - 如果 selected[j] 为 False，则将该元素加入 path，标记为已选，递归 dfs(i+1)，然后回溯：取消标记并弹出元素。
从 dfs(0) 开始搜索。
返回 ans。

代码实现

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = []
        selected = [False] * n

        def dfs(i):
            if i == n:
                ans.append(path[:])
                return
            for j, select in enumerate(selected):
                if not select:
                    path.append(nums[j])
                    selected[j] = True
                    dfs(i+1)
                    selected[j] = False
                    path.pop()

        dfs(0)
        return ans

📊 性能分析

时间复杂度： $O(n \times n!)$ ，共有 $n!$ 个排列，每个排列复制到结果需要 $O(n)$ 时间。
空间复杂度： $O(n)$ ，递归栈深度为 $n$ ，外加标记数组和路径存储。

思考

该解法是生成全排列的标准回溯模板，通过 selected 数组记录元素是否被使用，确保每个元素在排列中恰好出现一次。
优点：

逻辑清晰，易于理解和实现。
适用于元素互不重复的场景。

注意事项：

遍历时每次循环都扫描整个 selected 数组，复杂度为 $O(n^2 \times n!)$ ？实际每次递归调用都会扫描 $n$ 个位置，总递归节点数为 $n! \times n$ （每个排列生成过程中的节点数），因此总时间复杂度为 $O(n \times n!)$ （复制结果另算），在 $n \leq 6$ 时完全可行， $n=7$ 时 $7! = 5040$ ，仍可接受。
若 nums 中包含重复元素，此方法会产生重复排列，需另外处理（如排序 + 剪枝）。