1 """
 2 Given a collection of distinct integers, return all possible permutations.
 3 Example:
 4 Input: [1,2,3]
 5 Output:
 6 [
 7   [1,2,3],
 8   [1,3,2],
 9   [2,1,3],
10   [2,3,1],
11   [3,1,2],
12   [3,2,1]
13 ]
14 """
15 """
16 本题用回溯法。
17 关键用了一个used数组存储nums中的数字是否被使用过
18 有关回溯法可以有个专题
19 B站视频：https://www.bilibili.com/video/av76286065?from=search&seid=10714180800656978405
20 传送门：https://blog.csdn.net/qq_17550379/article/details/82500364
21 题号：46,47
22 """
23 
24 class Solution:
25     def permute(self, nums):
26         res = []
27         if not nums:
28             return res
29         used = [False] * len(nums)  # !!!关键所在
30         self._permute(nums, list(), res, used)
31         return res
32 
33     def _permute(self, nums, p, res, used):
34         if len(p) == len(nums):  # 保存条件
35             return res.append(p.copy())
36         for i, num in enumerate(nums):
37             if used[i]:  # ！！！
38                 continue
39             p.append(num)
40             used[i] = True
41             self._permute(nums, p, res, used)
42             p.pop()  # bug p.pop(0)是第一个元素,pop()是最后一个元素,栈
43             used[i] = False