47. 全排列 II [medium]

https://leetcode-cn.com/problems/permutations-ii/

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

示例:

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

通过次数74,324 | 提交次数124,978

First Try

2020-07-27

使用level_visited进行标记，确保子序列里某一idx的选择中每个元素只允许出现一次。

虽然backtrack已经写得很熟练，但如何标记nums列表里的元素已经被访问过还是纠结了一会儿。另外就是对重复项的去除，好像也没什么有效的经验。

上一次类似的好像是排序后进行处理0040题，统计每次允许出现的元素的重复次数，但并不在乎子序列里的元素排序。这次子序列里的元素位置改变又是新的情况，就变得棘手了起来。

visited防止的最好是index而不是数值本身，因为虽然不允许重复数列，但是一个数列还是允许几个重复元素的。避免重复数列，也就是如果遍历过程中某个位置已经选择了某个元素，在这轮遍历中就不要在相同位置继续选择相同的元素了，不然显然就是重复。从index为0的地方开始思考最清楚了，比如[1, 1, 2]，选择第一个1开头，就不要选择第二个1继续作为开头了，可以选择2作为下一个开头。

anyway, 处理过一波又涨了套路经验。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        def backtrack(nums, selected, seq, rv):
            if len(seq) == len(nums):
                rv.append(seq[:])
            level_visited = set()  # 一层被访问过，就不要再访问了
            for i in range(len(nums)):
                if nums[i] in level_visited or i in selected:
                    continue 
                level_visited.add(nums[i])
                seq.append(nums[i])
                selected.add(i)
                backtrack(nums, selected, seq, rv)
                seq.pop()
                selected.remove(i)

        if not len(nums):
            return []

        # nums = sorted(nums) #不排序也没问题，使用level visited进行标记了
        rv = []
        backtrack(nums, set(), [], rv)
        return rv 
        

执行用时：56 ms, 在所有 Python3 提交中击败了53.83%的用户
内存消耗：13.9 MB, 在所有 Python3 提交中击败了9.09%的用户

47. 全排列 II [medium]​

First Try​

47. 全排列 II [medium]

First Try