每天一道算法题：47. 全排列 II

算法题：47. 全排列 II"/>

每天一道算法题：47. 全排列 II

难度

中等

题目

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

示例 1:

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2:

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

思路

和 46 题类似但是不能有重复的解，46是数组中的元素各不相，不需要考虑重复元素，直接进行全排列。
47是数组中的元素可能包含重复，为了避免生成重复的全排列，需要在回溯的过程中跳过相邻的重复元素。数组中可能出现重复的数字，但是结果中不能出现重复的解，在处理过程中就要进行去重和剪枝。
首先对 nums 数组进行排序，在递归的过程中，添加了一个额外的集合 position 来跟踪已经选择的元素，并在回溯过程中进行去重的操作。

代码

from typing import Listclass Solution:def subsets(self, nums: List[int]) -> List[List[int]]:# 先排序，让重复的数在一块self.nums = sorted(nums)self.result = []self.length = len(self.nums)self.position = [False] * self.lengthself.backtrack([])return self.resultdef backtrack(self, tmp):if len(tmp) == len(self.nums):self.result.append(tmp[:])returnfor i in range(len(self.nums)):# 当前元素与上一位元素相同，并且上一位元素已经用过了 就跳过， 层 去重复if i > 0 and self.nums[i] == self.nums[i - 1] and self.position[i - 1]:continue# 如果当前的元素已经用过了，就跳过 枝去重if self.position[i]:continuetmp.append(self.nums[i])self.position[i] = Trueself.backtrack(tmp)tmp.pop()self.position[i] = Falseif __name__ == '__main__':nums = [1, 1, 2]s = Solution()s.subsets(nums)