全排列

🟡 Medium · 🏷️ 数组、回溯 · LeetCode#46

📖 题目

给一个不含重复数字的数组，返回它所有可能的全排列。

输入	输出
nums=[1,2,3]	6 种排列，如 [1,2,3]、[1,3,2]……

💡 思路

跟子集是同一套回溯框架，但两个关键点反过来了：

	子集	排列
[1,2] 和 [2,1]	算同一个	算两个不同结果
怎么避免重复	start 只往后选	not in path 跳过已经用过的
什么时候记录	每个节点	只在叶子节点（len(path)==n）

排列允许"回头"选之前跳过的数（比如选了2之后还能选1），所以不能用 start 限制方向；但同一个数在一条路径里只能用一次，所以每层都要检查 num not in path，跳过已经用过的。子集在每个节点都是合法答案，排列只有走满 n 个位置（到达叶子）才是一个完整排列，中间的路径都不算数。

💻 代码

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        n = len(nums)

        def backtrack(path):
            if len(path) == n:
                result.append(path[:])
                return
            for num in nums:
                if num not in path:
                    path.append(num)
                    backtrack(path)
                    path.pop()

        backtrack([])
        return result

时间复杂度 O(n × n!)，n! 个排列，每个要复制长度 n；空间复杂度 O(n)，递归深度加 path 长度。num not in path 是 O(n) 的线性扫描，可以用 set 优化到 O(1)，但这题 n 很小（通常 ≤ 6），影响可以忽略。