全排列
https://leetcode.cn/problems/permutations/description/
这是一道回溯问题，全排列本身有阶乘个答案，固定了最高位之后，后面的依次位进行全排列。所以可以想到：
- 大概需要一个for循环来遍历每一个位置，但是每个位置的数字不能是一样的，并且前面用过了后面就不能再用了。
- 需要让各个数字在每一个位置都尝试一遍
以上两个加起来发现需要用递归来解决，递归可以解决在解决后面的数字时前面的数字保持不变，并且需要不断地进行回溯尝试
以下是一个普通的回溯解法，用一个visited数组来记录数字有没有被用过。
递归里面首先，如果我们生成的排列数已经用完了所有的数字，说明这一把递归已经到最深了，就可以保存答案退出了，并且这里要注意，答案往里面加的时候，要用浅拷贝或者深拷贝，浅拷贝是成本最低的，深拷贝是最保险的。如果不用这俩拷贝，相当于只放了个引用，原数组一改，答案也改了。
接下来，如果没用完，那么就需要排列，我们对每一个数字都应该在每一个位置上进行探测，如果之前用过了就跳过，如果之前没用过，就把他放到结果后面，然后再继续递归往深走，但是退出来之后要把之前试的数字取消掉，因为可能那个位置还能放其他数字，不只是放某一个。
在递归之前，打个标，证明已经开始用这个数字了，递归之后，要把这个数字重新改为没用过
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
visited = [False] * len(nums)
res = []
self.backtrack(nums, [], res, visited)
return res
def backtrack(self, nums, current, res, visited):
if len(current) == len(nums):
res.append(current[:])
else:
for i in range(len(nums)):
if not visited[i]:
current.append(nums[i])
visited[i] = True
self.backtrack(nums, current, res, visited)
current.pop()
visited[i] = False