算法题: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)
更多推荐
每天一道算法题:47. 全排列 II
发布评论