此外还需设置一个特殊条件来排除重复结果:used[i] or i-1 >= 0 and nums[i-1] == nums[i] and not used[i-1]
used[i]表示i如果使用了,跳过,很好理解
i-1 >= 0 and nums[i-1] == nums[i] and not used[i-1]表示看前一位,若与当前相等,且前一位未使用过,则跳过。例如对nums=[1,1,1,2],三个1是重复元素,取的时候应该作为一个整体取,即nums的0,1,2号,否则会出现重复结果。上面条件的限制使得nums[1]只有在nums[0]出现的时候才取,同理nums[2]只有在nums[1]出现的时候才取,因此保证了结果中三个1的取用先后次序为nums的0,1,2号。
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
self.res = []
tmpList = []
used = [False] * len(nums) #标记数组
nums.sort()
self.backtrack(nums, tmpList, used)
return self.res
def backtrack(self, nums, tmpList, used):
if len(tmpList) == len(nums):
self.res.append(list(tmpList))
for i in range(len(nums)):
#注意复杂条件,最后一个可改为used[i-1]
if used[i] or i-1 >= 0 and nums[i-1] == nums[i] and not used[i-1]:
continue
used[i] = True
self.backtrack(nums, tmpList + [nums[i]], used)
used[i] = False #还原现场
另一种思路:
若重复数字1,1,1中有一个(如第二个)被使用了,则下次选择不选第二个1前面的1,只能往后选:
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def dfs(tmp, used):
if len(tmp) == n:
res.append(list(tmp))
else:
for i in range(n):
if used[i]: #使用过则跳过
continue
else: #若未使用过,看i右边是否有相等且使用过的数字
j = i
while j+1 < n and used[j] == False and nums[j] == nums[j+1]:
j += 1
if used[j]: #若有则跳过
continue
used[i] = True
dfs(tmp + [nums[i]], used)
used[i] = False
nums.sort()
n = len(nums)
used = [False] * n
res = []
dfs([], used)
return res