1. 题目：
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
2. 我的代码：
class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: # 回溯 path = [] result = [] def backtracking(rest): # 终止条件 if rest == []: result.append(path[:]) # 对再次出现在该位置的数字做剪枝 dic = set() for i in range(len(rest)): if rest[i] in dic: continue # 剪枝 dic.add(rest[i]) path.append(rest[i]) backtracking(rest[:i] + rest[i + 1:]) path.pop() backtracking(nums) return result
这个题继续使用回溯算法，只不过要配合剪枝操作。在每一层定义一个set作为遍历过的元素的记录，如果不在记录中则可以递归，如果在记录中则直接剪枝，continue。
为什么要剪枝呢，因为如果相同元素在次位置再递归一次，则会产生和之前递归过的一模一样的分支。继续将遍历完整个列表作为终止条件即可。
以树形结构展示为下图：
