（补）算法刷题Day19：BM55 没有重复项数字的全排列

题目链接

给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

思路：

使用回溯，每次选择一个数字，画出回溯二叉树。回溯的过程中，如果收集过该元素，就跳过，不用对其进行回溯。我这里是通过该元素是否在path数组中出现过来筛选的，也可以用通用一点的used数组记录哪些元素被使用过。（这个used在Day20的题目用到）。

代码

import copyresult = [] # 全局元素，记录收集好的路径
def traverse(nums, path):if len(path) == len(nums): // 当收集的路径长度等于num长度时，即为收集好了tmp = copy.deepcopy(path) // 注意，一定要使用深拷贝result.append(tmp)returnfor i in range(len(nums)):if nums[i] in path: //如果收集过，就跳过。用是否在数组中出现过来筛选。continueelse:path.append(nums[i])traverse(nums, path)path.pop()class Solution:def permute(self, num: List[int]) -> List[List[int]]:traverse(num, [])return result

隔三差五还债，终于忙完家里的事情，有精力去刷题了