原題
給出一個(gè)具有重復(fù)數(shù)字的列表砍鸠，找出列表所有不同的排列
給出列表[1,2,2]，不同的排列有：
[
[1,2,2],
[2,1,2],
[2,2,1]
]
解題思路
- 首先數(shù)組排序耕驰，跳出recursion條件為
len(path) == len(num) - 設(shè)置一個(gè)flag數(shù)組爷辱，來(lái)判定一個(gè)元素是否被訪問(wèn)過(guò)
- 如果
previous沒(méi)有被訪問(wèn)，而且current == previous，則會(huì)出現(xiàn)重復(fù)饭弓，所以跳過(guò)
完整代碼
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
flags = [False] * len(nums)
self.permuteForReal(sorted(nums), result, flags, [])
return result
def permuteForReal(self, num, output, flags, path):
if len(path) == len(num):
output.append(path[:])
return
for i in range(len(num)):
if not flags[i]:
if i != 0 and not flags[i-1] and num[i] == num[i-1]:
continue
path.append(num[i])
flags[i] = True
self.permuteForReal(num, output, flags, path)
path.pop()
flags[i] = False
