Leetcode47：全排列 II

题目描述：

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

代码思路：

1. 排序：
   • 首先对输入数组 nums 进行排序。排序的目的是为了将相同的元素放在一起，这样在回溯过程中可以方便地跳过它们，以避免生成重复的子集。
2. 回溯函数 backtrack：
   • backtrack 函数是递归生成所有子集的核心。它接受两个参数：start 表示当前遍历的起始索引，path 表示当前构建的子集路径。
3. 添加当前路径到结果中：
   • 在每次递归调用之前，首先将当前的 path（子集）添加到结果列表 res 中。这是因为在回溯过程中，path 会不断增长，但我们需要记录所有可能的中间状态作为子集。
4. 遍历数组：
   • 从 start 开始遍历数组 nums。对于每个索引 i，尝试将 nums[i] 添加到当前路径 path 中。
5. 跳过重复元素：
   • 在添加元素之前，检查当前元素 nums[i] 是否与前一个元素 nums[i - 1] 相同，并且前一个元素是在当前递归层级之前被考虑的（即 i > start）。如果是，则跳过当前元素，以避免生成重复的子集。
6. 选择当前元素：
   • 如果当前元素不是重复元素（或者它是第一次在当前层级被考虑），则将其添加到 path 中。
7. 递归调用：
   • 递归调用 backtrack 函数，继续从 i + 1 开始构建子集。这一步是深度优先搜索的体现，尝试所有可能的后续元素组合。
8. 回溯：
   • 在递归返回之前，需要从 path 中移除刚刚添加的元素。这是回溯法的关键步骤，允许算法探索不同的选择路径，而不影响之前的状态。
9. 初始化结果列表和启动回溯：
   • 在 Solution 类的 subsetsWithDup 方法中，初始化一个空列表 res 用于存储所有子集。然后调用 backtrack(0, []) 开始回溯过程，从索引 0 开始，路径初始化为空列表。
10. 返回结果：
    • 最后，返回存储所有子集的结果列表 res。

代码实现：

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans, n = [], len(nums)
        vis = {i: False for i in range(n)}

        def dfs(i: int, path: list):
            if i == n:
                ans.append(path)
                return
            
            for j in range(n):
                if vis[j] or j and nums[j] == nums[j - 1] and not vis[j - 1]:
                    continue
                vis[j] = True
                dfs(i + 1, path + [nums[j]])
                vis[j] = False
        dfs(0, [])
        return ans