LeetCode link
Time complexity O(n * n!)
The case where a repeating element is added to the full permutation , And the results should not be repeated
Ideas ：
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res_list = []
path = []
nums_len = len(nums)
# An array of tags of the same size To mark whether a subscript has been selected
selected = [False for _ in range(nums_len)]
def doit():
if len(path) == nums_len:
res_list.append(path[:])
return
for i in range(nums_len):
if not selected[i]:
# Because I've been right nums Array is out of order here nums[i] == nums[i - 1] Indicates that it may be a duplicate Branch
# But there are two cases With [1,1,2] give an example
# situation 1、 The first layer selects i=0 Situated 1 The second layer chose i=1 Situated 1 This is normal Should not be excluded
# situation 2、 The first layer selects i=1 Situated 1 This is a duplicate branch Need to skip
# therefore , Just judge nums[i] == nums[i - 1] Still not enough
# With the help of selected Array
# situation 1 nums[i] Although and num[i - 1] equal however selected[i - 1] is True indicate nums[i - 1] It was selected on the upper floor here num[i] Can be selected normally
# situation 2 select[i - 1] is False It shows that this is a repeated situation Should exclude
if i > 0 and nums[i] == nums[i - 1] and not selected[i - 1]:
continue
# Mark selected
selected[i] = True
# add value
path.append(nums[i])
doit()
# Roll back
path.pop()
selected[i] = False
# Sort first to ensure that repeated elements are close together So you can see nums[i] Whether and nums[i - 1] Equal to judge whether to repeat
nums.sort()
doit()
return res_list
