建议先完成第一题 Permutations:
解法一:使用一个 hashtable 对象或者 set 对象,重复的元素不要放到结果中。只需要在第一题的基础加上一个判断即可。
解法二:我们可以观察到,解法一在数组中包含多个重复元素的时候会有很多重复遍历,所以在最开始的遍历时,跳过重复元素,举例:
Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]
当我们对第一个 1 进行 DFS 遍历之后,不需要对第二个 1 进行遍历(因为结果一定都和第一个 1 的一样),所以我们可以这样实现 pseudocode:
def permuteUnique(nums):
# 记录遍历过的元素
seen = set()
res = []
for i in length of nums:
if nums[i] not in seen:
# 对第一次出现的元素进行遍历
dfs(nums[:i]+nums[i+1:], [nums[i]])
# 记录
seen.add(nums[i])
return res
def dfs(nums, path):
# 结束条件
if not nums:
# 特殊情况
# [1, 2, 2]
# 此时遍历第一个 1 的时候,第一个 2 和第二个 2 位置调换,会得到同样的两个 [1, 2, 2]
# 所以需要判断现在得到的结果是不是已经存在
if path not in res:
self.res.append(path)
return
# 每次从数组选一个元素,加到可能的结果中
for i in range(len(nums)):
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]])