给定一个不含重复数字的数组 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个数[1,2,3],你会第一位先排1，然后第二位只能是2或者3，如果第二位是2，第三位只能是3了…如果数字很多，那么使用循环穷举，嵌套的层级会非常繁琐。
方法二：我们可以借鉴【回溯算法】羊娃找羊的路线图，画出全排列的树图，如下：
我们从根节点遍历这棵树，记录下走过路径的数字，走到叶子节点，就可以得到一个排列啦。然后后退，去走其他分支，直到走完所有的叶子节点，那就可以得到全排列啦。
那么这棵树图是怎么得到的？
为了方便理解，我们可以把nums个数k看做k种选择，比如对于[1,2,3]，每一位都有3种选择：1、2、3。
每一次做选择，都展开出一棵空间树，选择完后，如果是重复选的路径，就做剪枝。
好啦，现在知道树怎么来的，我们来看下怎么遍历找到全排列呢？每次走树的分支，都像是在做决策。我们可以把已走的路径和可做的选择作为树节点的两个属性。
如果在根节点，可做的选择为1、2、3，走过的路径为空，如下图
走到叶子节点时，已走路径数组长度等于原素组的个数，这时候走过路径就是满足条件的一个解。
代码实现：
这道题用到递归。
递归入口：是一个可选路径和已走过的路径。
递归函数体：一个for循环，枚举当前数组的元素，并且需要if判断，以跳过剪枝
递归出口：也就是走到叶子节点啦，叶子节点，就是当构建的已走路径path的数组长度等于nums的长度
#全排列数组存储最终结果
res=[]
def backtrack(nums, path, used):
global res
#已走路径path的数组长度等于nums的长度,表示走到叶子节点，所以加到全排列集合
if len(path) == len(nums):
res.append(path.copy())
return
for i in range(len(nums)):
# 剪枝，排查已经走过的路径
if used[i]:
continue
# 做选择,加到当前路径
path.append(nums[i])
#标记已使用
used[i] = True
#递归，进入下一层的决策
backtrack(nums, path, used)
# 撤销选择
path.pop()
used[i] = False
def permute(nums):
global res
# 记录路径
path = []
# 标记选择是否被使用
used = [False] * len(nums)
#递归函数入口，可做选择是nums数组
backtrack(nums, path, used)
return res
回溯过程如图
为什么用到回溯算法呢？
因为我们不是要找到一个排列就好了，而是需要找出所有满足条件的排列，当递归调用结束时，结束的是当前的递归分支，还需要去别的分支继续找，因此需要撤销当前的选择，回到选择前的状态，再选下一个选项，即进入下一个分支。
回溯算法框架
决策一个回溯问题，实际上就是解决一个决策树的遍历过程。需要考虑这三个问题：
1、已走路径：已做出选择，走过的路径
2、可选列表：你当前可以做的选择
3、结束条件：一般走到决策树的叶子节点，它无法再做别的条件选择
本站内容未经许可，禁止任何网站及个人进行转载。
