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

Reference

题解

此处使用BFS算法。将数组排序后，每次取出一个数值。假设已经构造好前\(k\)个值的全排列，新取出的数值可以加入到\(k\)个元素的全排列的每个位置，得到\(k+1\)个值的全排列。注意对重复数值的处理，当新加入的数和后一个数相同时，为了避免生成重复的排列，需要跳过后续所有的遍历流程。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        sorted_nums = sorted(nums)
        result = [[]]
        step = 0
        for num in sorted_nums:
            new_result = []
            for record in result:
                for pos in range(step + 1):
                    # Insert Element
                    new_result.append([*record[:pos], num, *record[pos:]])
                    # Skip if duplicate
                    if pos < step and record[pos] == num:
                        break
            step += 1
            result = new_result
        return result

评论