46. 全排列

题目链接：46. 全排列

题目描述

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

核心思考：回溯搜索 (Backtracking) 的经典试炼

排列问题需要尝试枚举出将各个字符作为头兵尾巴的所有填法，是理解回溯思想的基石题：通过深入路径并在穷尽后将痕迹倒逼重置擦除。

1. 当前路径记录：这里用一只外部列表 path 用于随时跟踪搜集下当前已招募登记下哪些队员编号！
2. 退出收割结果边界：由于需要全数组所有人参与构建队列组合排列方案才算彻底完整的一案，于是我们依靠 len(path) == len(nums) 将其作为终止递归并提取收容回结果册 res 的判定阈值点。
3. 回溯三部曲循环开展：
   • 每到一个深度都要全横向重新看是否有未上场的英雄选派：依靠判断这名入选的角色是否在此刻这队 path 已挂名 (if num in path: continue) 排除已经身处阵中的分身重影。
   • 不重复即可执行尝试派遣出战（入录 path.append）；并在决定之后往更后续深度放开委托下沿搜索 dfs() 继续探路。
   • 深陷后折返或者一无所获回归，此时是该尝试在这一层派遣其他的平替角色了。绝不可继续沿用当前留下的污渍痕迹，必须原道收还交出现场重置 (path.pop) 。

切片防空大坑：压入名册集合时千万不能直接 res.append(path)。path 一直都是同一个引用包裹空间在倒腾增减，如若不借助切片技术 path[:] 做断层影像浅拷贝留影锁死记录的话，退守扫尾 pop 将它还原掏空时也会导致记录表上的资料离奇空化蒸发。

解题思路 (Python)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def dfs():
            if len(path) == len(nums):
                # 传入 path 的浅拷贝，否则后续的 pop 操作会清空已被加入 res 的列表
                res.append(path[:]) 
                return
            for num in nums:
                if num in path:
                    continue
                path.append(num)
                dfs()
                path.pop()
        dfs()
        return res

复杂度分析

• 时间复杂度：O(N * N!)，全排列数学产生的所有组合方案总数天衣无缝天然的底线边界在 N 阶乘 $N!$，每从分支产出一枚合格结果在录入拷贝并转移时还有需要执行浅拷贝承受 O(N) 规模的同步拷贝劳作负担，属于呈爆炸暴涨开销的算法。
• 空间复杂度：O(N)，调用回溯过程中在内存主记录和栈体深度压下的单向路径最大跨长不会超出该组全配数字阵容 O(N)；这不包含输出本身要求庞大的 O(N * N!) 驻扎。