Article From:https://www.cnblogs.com/zzq-123456/p/9969854.html

@author: ZZQ
@software: PyCharm
@file: permuteUnique.py
@time: 2018/11/16 13:34
Requirement: Given a sequence of repetitive numbers, return all non-repetitive full permutations.
Example:
Input: [1, 1, 2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Thought: Deep search, and then remove the unsatisfactory conditions
Deduplication process:
1. Every time you search down, you remove the parent node element
2. Make a mark for each element to indicate whether the current element has been used or not, and if it has been used, end the downward search.
3. Judge whether the adjacent same element has been used or not, and if it has been used, skip the element.

``````import copy
class Solution():
def __init__(self):
tt_ans = []
pass

def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
temp_ans = []
nums.sort()
length = len(nums)
if length == 0 or nums == []:
return []
flag = []
for i in range(length):
flag.append(0)
cur_length = 0
start_index = -1
self.dfs(temp_ans, start_index, nums, flag, cur_length, length, ans)
return ans

def dfs(self, temp_ans,start_index, nums, flag, cur_length, length, ans):
if cur_length == length:
tt_ans = copy.deepcopy(temp_ans)
ans.append(tt_ans)

else:
for i in range(length):
if i > 0 and nums[i] == nums[i - 1] and flag[i - 1] == 1:
continue
if i != start_index and flag[i] == 0:
temp_ans.append(nums[i])
flag[i] = 1
self.dfs(temp_ans, i, nums, flag, cur_length+1, length, ans)
temp_ans.pop()
flag[i] = 0``````