目录

题目链接

题目描述

示例

解决思路

---

题目链接

47 Permutations II

题目描述

给定一系列数字组成的列表nums，列表中可能会含有重复数字，返回列表元素的所有不重复排列结果。

示例

输入：nums = [1,1,2]

输出：[[1,1,2] , [1,2,1] , [2,1,1]]

输入：nums=[1,2,3]

输出：[ [1,2,3] , [1,3,2] , [2,1,3] , [2,3,1] , [3,1,2] , [3,2,1]]

解决思路

这个问题是46 Permutations问题的扩展，将这个问题看作树的深度优先搜索更好理解。如对于示例中的[1,1,2]，对应要遍历的树为

在完成第二层第一个子节点[1]的深度优先搜索后，能够得到[1,1,2],[1,2,1]两种组合，第二层第二个子节点也为1，如果把这个子节点当作父节点往下进行深度优先遍历的话，会得到重复的元素组合。因此在用for循环体遍历同层节点前要对该层节点进行排序，使相同的元素能够左右相邻，同时对于这种情况（i!=0 and nums[i] == nums[i-1]）要利用continue关键字跳过。

Python实现

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:def duplicate_dfs(nums,path,return_list):if not nums:return_list.append(path) #深度优先搜索到了最后一层，将得到的路径添加到最后返回的return_list中。else:#对子节点列表进行排序，这样相等的数字会左右相邻nums.sort()for i in range(len(nums)): #同层元素遍历if(i != 0 and nums[i] == nums[i-1]):#如果同层元素中后一个元素和前一个元素相等，就要把这个元素跳过去。 continueduplicate_dfs(nums[:i]+nums[i+1:],path+[nums[i]],return_list) #深度优先搜索return_list = []duplicate_dfs(nums,[],return_list)return return_list