题目描述

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]

题目解析

本题也就是全排列的基础上增加了一个去重。不过需要注意的是在删除元素的时候一定要删除最后一个，不要用remove，因为remove会优先删除第一个找到的。具体去重的思想为回溯剪枝，也就是遇到前面已经搜索过的就不再搜索了。不过，简单的去重后来发现会出超时，所以应该考虑更加深入的剪枝。

剪枝思路：对于每一层的结点，如果已经有上一个结点加入过搜索树，那这一层就不需要再添加该结点了。用一个临时变量temp来存储已经有过搜索的结点，如果当前结点等于temp，就说明前面已经搜索过该结点，如果不等于，说明还没有搜索过，继续搜索。具体代码如下：

代码解答（py）

import copy res = [] class Solution(object): def permuteUnique(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ res.clear() if len(nums) == 0: return [] if len(nums) == 1: return [nums] for i in range(len(nums)): self.permuteHelper([nums[i]], nums[0:i] + nums[i + 1:]) return res def permuteHelper(self, before, nums): now = copy.deepcopy(before) if len(nums) == 1: now.append(nums[0]) if now not in res: res.append(now) else: temp = -99991 for i in range(len(nums)): if temp != nums[i]: now.append(nums[i]) self.permuteHelper(now, nums[0:i] + nums[i + 1:]) now.pop() temp = nums[i]代码思路：res作为最后的结果集，nums先排序，进入Helper，递归返回条件是搜索到最后一个数了，如果后面的数字还比较多，可以用temp来作为临时变量，然后temp比较此时的搜索，如果不等于说明该点还没有被搜索过，然后开始搜索。最后在每一层都有剪枝。