全排列 II

难度: Medium

给定一个可包含重复数字的序列 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

Submission

运行时间: 52 ms

内存: 15.3 MB

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

        def backtrack(path):
            if len(path) == len(nums):
                ans.append(list(path))
                return

            for i in range(len(nums)):
                if i > 0 and nums[i] == nums[i-1]:
                    continue
                if nums[i] is None:
                    continue
                path.append(nums[i])
                nums[i] = None
                backtrack(path)
                nums[i] = path.pop()

        backtrack([])
        return ans

Explain

这个题解使用了回溯算法。首先对数组进行排序，然后使用递归的方式生成所有排列。为了避免生成重复的排列，在每一层递归中，如果当前元素和前一个元素相同，则跳过该元素。另外，为了避免在递归过程中重复使用同一个元素，使用 None 标记已经使用过的元素。

时间复杂度: O(n * n!)

空间复杂度: O(n * n!)

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()  # 对数组进行排序

        def backtrack(path):
            if len(path) == len(nums):
                ans.append(list(path))  # 生成了一个完整的排列，将其添加到结果列表中
                return

            for i in range(len(nums)):
                if i > 0 and nums[i] == nums[i-1]:  # 如果当前元素与前一个元素相同，跳过该元素以避免生成重复的排列
                    continue
                if nums[i] is None:  # 如果当前元素已经被使用过，跳过该元素
                    continue
                path.append(nums[i])  # 将当前元素添加到当前排列中
                nums[i] = None  # 将当前元素标记为已使用
                backtrack(path)  # 递归生成下一个元素的排列
                nums[i] = path.pop()  # 回溯，将当前元素从排列中移除，并将其标记为未使用

        backtrack([])
        return ans

Explore

在回溯算法中对数组进行排序是为了更方便地处理重复元素。当数组排序后，相同的元素会被排列在一起。这样，在生成排列的过程中，可以通过简单的比较相邻元素来检查是否存在重复的元素。如果当前元素与前一个元素相同，可以直接跳过这个元素，从而避免生成重复的排列。这种方法简化了重复检测的逻辑，使得代码更简洁且有效率。

使用`None`来标记已经使用过的元素是一种有效的方法，但不一定是最优的方法，因为它修改了原数组的值，可能在某些情况下引起混淆或错误。其他常见的方法包括使用一个布尔数组（或位图）来追踪每个元素的使用状态。这种方法不需要修改原数组，而是通过额外的空间来记录哪些元素已被使用过，这样可以保持原数组不变，逻辑上可能更清晰。

此方法确保了所有不重复的全排列都被正确生成，并没有漏掉任何排列。通过先排序再检查相邻元素是否相同，这种策略确保只有当相同的元素第一次出现时才会被考虑进排列中，而在相同元素的连续序列中，只有第一个元素会被用来生成新的排列。这样做可以避免重复而不会错过任何合法的排列组合。

这一步是回溯算法的核心部分，称为回溯。在递归调用`backtrack`之后执行`nums[i] = path.pop()`是为了撤销之前做出的选择，即将当前元素从路径中移除并恢复其在数组中的值，使得这个元素在后续的迭代中可以重新被使用。这样做确保了在每一层递归中，路径和数组的状态都被正确地管理和恢复，使算法能够正确地探索所有可能的排列组合。