回溯——10.全排列 II

力扣题目链接

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

示例 1：

• 输入：nums = [1,1,2]
• 输出： [[1,1,2], [1,2,1], [2,1,1]]

解题思路：

1. 排序：首先对数组进行排序，目的是为了方便后续跳过相同元素，避免产生重复的排列。
2. 回溯法：使用递归回溯法生成排列。在生成过程中，依靠“已使用标记数组”（used）记录当前元素是否已经被选过。同时，利用条件判断跳过重复元素。
3. 避免重复：通过检查相邻元素是否相同且前一个未使用来避免生成重复的排列。

完整代码如下：

class Solution:def permuteUnique(self, nums):nums.sort()  # 排序result = []self.backtracking(nums, [], [False] * len(nums), result)return resultdef backtracking(self, nums, path, used, result):if len(path) == len(nums):result.append(path[:])returnfor i in range(len(nums)):if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:continueused[i] = Truepath.append(nums[i])self.backtracking(nums, path, used, result)path.pop()used[i] = False

class Solution:def permuteUnique(self, nums):nums.sort()  # 排序result = []  # 保存结果的列表self.backtracking(nums, [], [False] * len(nums), result)  # 调用回溯函数return result  # 返回所有可能的排列

• nums.sort()：先对nums进行排序，使得相同的元素相邻。排序的目的是在回溯过程中通过相邻重复元素的判断来跳过重复的排列。
• result = []：初始化空列表，用于存放最终的全排列结果。
• self.backtracking(nums, [], [False] * len(nums), result)：调用backtracking方法。参数说明：
  • nums：排序后的输入数组。
  • []：当前的排列路径，初始为空。
  • [False] * len(nums)：used数组，用于记录每个元素是否已经在当前排列中使用。初始时，每个元素都没有使用，故全为False。
  • result：用于保存最终的所有不重复排列。

    def backtracking(self, nums, path, used, result):if len(path) == len(nums):result.append(path[:])  # 将当前路径加入结果return

if len(path) == len(nums)：当path中元素数量等于nums的长度时，说明已经生成了一组完整的排列。将path的副本（path[:]）添加到result中，并返回终止当前递归。

        for i in range(len(nums)):if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:continue

• for i in range(len(nums))：遍历数组nums中的每个元素，尝试将其加入当前排列路径path中。
• if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]：这一行用于跳过重复元素和已经使用过的元素。
  • i > 0 and nums[i] == nums[i - 1] and not used[i - 1]：当当前元素nums[i]与前一个元素相同，且前一个元素未被使用时，跳过当前元素以避免重复排列。
  • used[i]：如果当前元素nums[i]已经在路径中被使用，则跳过它。

            used[i] = True  # 标记当前元素为已使用path.append(nums[i])  # 将当前元素加入路径self.backtracking(nums, path, used, result)  # 递归调用回溯path.pop()  # 回溯，移除最后一个元素used[i] = False  # 撤销使用标记

• used[i] = True：标记当前元素nums[i]为已使用。
• path.append(nums[i])：将当前元素添加到路径中，生成新的部分排列。
• self.backtracking(nums, path, used, result)：递归调用backtracking，继续生成排列。
• path.pop()：回溯时，移除路径中最后一个添加的元素，以便尝试其他可能的排列。
• used[i] = False：撤销当前元素的已使用标记，供后续的排列尝试。