1、题目描述

https://leetcode-cn.com/problems/permutations-ii/

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

2、代码详解

相关题：回溯-LeetCode46. 全排列（不重复的数字）  https://blog.csdn.net/IOT_victor/article/details/107072205

加入 nums[i] == nums[i-1] 判断nums.sort() class Solution(object): def permuteUnique(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ # nums 选择列表，depth深度， path 路径，used 标记数组！，res 结果 def dfs(nums, size, depth, path, used, res): # 结束条件：nums 中的元素全都在 path 中出现 if depth == size: res.append(path[:]) # 需要传递下path的拷贝，否则对path的修改会影响到结果 return for i in range(size): # used[i]==False，表示未被用过 if not used[i]: # （新加判重）剪枝！！！ # 如果出现连续重复的字符,跳出for循环（必须操作，用例1,1，不然会输出["1,1","1,1"]） # 加上not used[i-1],这样的剪枝更彻底，不加也能通过 if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue # 做选择 used[i] = True path.append(nums[i]) # 进入下一层决策树 dfs(nums, size, depth + 1, path, used, res) # 撤销选择 used[i] = False path.pop() size = len(nums) if len(nums) == 0: return [] # （排序）在搜索之前就对候选数组排序 # 一旦发现这一支搜索下去可能搜索到重复的元素就停止搜索，这样结果集中不会包含重复元素 nums.sort() used = [False for _ in range(size)] res = [] dfs(nums, size, 0, [], used, res) return res nums = [1,1,2] s = Solution() print(s.permuteUnique(nums))

https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/