Use a DFS.
To avoid duplicate, we should use a counts and only use one value for one position once.
class Solution:
def permuteUnique(self, nums):
counts = {}
for num in nums:
if num not in counts:
counts[num] = 0
counts[num] += 1
return self._dfs(counts)
def _dfs(self, counts):
if len(counts) == 0:
return []
if len(counts) == 1 and list(counts.values())[0] == 1:
return [[list(counts.keys())[0]]]
res = []
for current in list(counts.keys()):
counts[current] -= 1
if counts[current] == 0:
counts.pop(current)
for child in self._dfs(counts):
res.append(child + [current])
if current not in counts:
counts[current] = 0
counts[current] += 1
return res