@author: ZZQ
@software: PyCharm
@file: permuteUnique.py
@time: 2018/11/16 13:34
要求：给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
思路：深搜，然后去掉不满足条件的
去重过程：
1. 每次向下搜索时，都去除掉父节点这个元素
2. 给每个元素做一个标记，来表示当前元素是否被用过，如果被用过，则结束向下搜索；
3. 判断相邻的相同元素知否被用过，如果用过则跳过该元素。
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