leetcode第47题，全排列的升级版，要求需要全排列的数组中有重复，输出去重后的结果。
这个题可以充分运用语言上的特点，比如先生成带有重复项的全排列，这在之前那道题目已经完成了，然后set一下去重，但是这样做太不自然了，复杂度肯定也会依赖于set去重操作，有没有自然去掉重复项的办法呢？
可以这样考虑，为什么会产生重复项，因为数组中含有重复数字。在每一轮深搜的时候，单独设置一个dict记录用到的数字，如果在碰到相同的数字出现，就会在字典里查出来，这就意味着这个数字不用再进行下一步dfs了，因为已经有一个和它完全相同的数字已经搜索了，这样就自然去重了。
class Solution(object): def permuteUnique(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ ans = [] def dfs(nums, ans, path): if not nums: ans.append(path) else: d = {} for i in xrange(len(nums)): if nums[i] not in d: dfs(nums[:i]+nums[i+1:], ans, path+[nums[i]]) d[nums[i]] = 1 nums.sort() dfs(nums, ans, []) return ans