leetcode47全排列2

题目

给定一个可包含重复数字的序列 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. 基本回溯法

使用交换的方式生成排列
每次固定一个位置，然后递归处理剩余位置
但这种方法会产生重复的排列

2. 回溯法+剪枝

在基本回溯的基础上添加剪枝条件
通过判断是否已经使用过相同的数字来避免重复
需要先对数组排序，使相同的数字相邻

代码实现

1. 基本回溯法

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(nums, start, end):
            # 当start等于end时，说明已经处理完所有位置
            if start == end:
                # 将当前排列加入结果集（注意要创建副本）
                res.append(nums[:])
            
            # 遍历从start到end的所有位置
            for i in range(start, end):
                # 交换当前位置start和位置i的元素
                nums[start], nums[i] = nums[i], nums[start]
                # 递归处理下一个位置
                backtrack(nums, start + 1, end)
                # 回溯：恢复交换前的状态
                nums[start], nums[i] = nums[i], nums[start]

2. 回溯法+剪枝

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(nums, start, end):
            # 递归终止条件：已处理完所有位置
            if start == end:
                # nums[:] 是 Python 的切片语法，用于创建列表的副本
                # 为什么需要创建副本？
                # 1. nums 是一个在回溯过程中不断变化的列表
                # 2. 如果直接使用 nums，添加的是引用，后续的修改会影响已经添加到结果中的排列
                # 3. 通过 nums[:] 创建新的列表，确保每个排列都是独立的
                # 例如：
                # - 如果写 res.append(nums)：
                #   nums = [1,2] → res = [[1,2]]
                #   nums变成[2,1] → res = [[2,1]] （之前添加的[1,2]也变了！）
                # - 使用 res.append(nums[:])：
                #   nums = [1,2] → res = [[1,2]]
                #   nums变成[2,1] → res = [[1,2], [2,1]] （之前的[1,2]保持不变）
                res.append(nums[:])  # 添加当前排列的副本
            
            # 记录这一层递归中已经使用过的数字
            used = set()
            
            for i in range(start, end):
                # 剪枝：如果当前数字已经在这一层使用过，跳过
                if nums[i] in used:
                    continue
                
                # 记录这个数字已经使用过
                used.add(nums[i])
                
                # 交换，递归，回溯
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(nums, start + 1, end)
                nums[start], nums[i] = nums[i], nums[start]
        
        res = []  # 存储所有排列结果
        backtrack(nums, 0, len(nums))
        return res