1、题目描述
给定一个不含重复数字的数组 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、先验知识
2.1 回溯算法
回溯法也可以叫做回溯搜索法，它是⼀种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。虽然回溯法很难，很不好理解，但是回溯法并不是什么⾼效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法⾼效⼀些，可以加⼀些剪枝的操作，但也改不了回溯法就是穷举的本质。
但是面对一些问题，能用穷举法求解已经是最优算法，比如以下问题：
-
组合问题：N个数里面按一定规则找出k个数的集合
-
切割问题：一个字符串按一定规则有几种切割方式
-
子集问题：一个N个数的集合里有多少符合条件的子集
-
排列问题：N个数按⼀定规则全排列，有几种排列方式
-
棋盘问题：N皇后，解数独等等
2.2 回溯算法模板（python)
def backtracking(参数):#参数可根据实际情况进行修整if(终止条件):收集结果returnfor (集合中的元素):处理节点递归回溯return3 全排列
3.1 思路
全排列的树结构可表示如下：
根据模板进行分析
（1)终止条件
当path的长度和nums的长度相同时，表示path已经得到了一个全排列组合，此时终止；
（2）收集结果
将终止时，path加入到结果res中，需要注意的是，由于回溯的撤销操作，path会不断发生改变，在添加结果时，应当使用path.copy()，防止后续修改影响已保存的结果；
（3）集合中元素
从给定的nums中进行选择
（4）处理节点
从nums中任选一个元素将其加入到path中
（5）递归
根据path的长度和变化的集合进行递归，变化的集合表示为s-{path}中已经存在的元素
（6）回溯
在 path[i] = x 赋值后，递归处理下一层。当递归返回时，当前层的循环继续执行，下一个 x 会直接覆盖 path[i] 的值，自然实现了状态的“回退”。因此，在本代码中无需显式撤销操作。
（7）参数
根据上述分析，可见递归的参数可表示为path的长度和变化的集合
3.2 完整代码
根据上述分析，可以得到完整代码：
class Solution:def permute(self, nums: List[int]) -> List[List[int]]:n = len(nums)res = []path = [0] * ndef backtracking(i,s):if i == n:res.append(path.copy())returnfor x in s:path[i] = xbacktracking(i+1, s-{x})backtracking(0,set(nums))return res
