目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

二、解题思路

DFS+回溯，注意m_dict存储数字的个数，每次都固定一个数字，然后找子排列。m_dict起到去重的作用。

三、代码

class Solution:def permuteUnique(self, nums: list) -> list:m_dict = {}n = len(nums)for num in nums:m_dict.setdefault(num, 0)  # only first is 0m_dict[num] += 1def dfs(index):if index == n:return [[]]res = []for num in m_dict:if m_dict[num] == 0:continuem_dict[num] -= 1# next num and index add 1res.extend([[num] + res for res in dfs(index + 1)])m_dict[num] += 1return resreturn dfs(0)if __name__ == '__main__':test = [1, 1, 2]s = Solution()ans = s.permuteUnique(test)print(ans)