全排列 II

题目描述
给定一个可包含重复数字的整数数组 nums，返回所有不重复的全排列。全排列要求将数组中的所有元素以一定的顺序排列，每个排列包含所有元素各一次，但需要排除重复的排列。

示例：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

解题过程

1. 问题分析与核心挑战

   • 与无重复数字的全排列（LeetCode 第 46 题）不同，本题数组可能包含重复数字。
   • 核心挑战是如何避免生成重复的排列。例如，对于 [1,1,2]，如果直接生成所有排列，会得到多个相同的 [1,1,2]。
   • 关键思路：在生成排列的过程中，通过一定的规则“剪枝”，跳过那些会导致重复排列的选择。

2. 基础方法：回溯法框架

   • 全排列问题通常使用回溯法（深度优先搜索）解决。
   • 基本框架是：从第一个位置开始，逐个位置选择数字。对于每个位置，尝试所有尚未被使用的数字。
   • 对于无重复数字的情况，只需用一个数组标记每个数字是否已被使用。

3. 处理重复数字的剪枝策略

   • 为了去除重复，我们需要确保在同一个位置上，相同的数字只被选择一次。
   • 具体步骤：
     a. 首先将数组排序，使得相同的数字相邻。
     b. 在选择数字时，如果当前数字与前一个数字相同，并且前一个数字没有被使用（即已经回溯撤销选择），则跳过当前数字。
     c. 解释：如果前一个相同的数字没有被使用，说明在当前层级（同一个位置）已经尝试过选择这个数字并完成了后续搜索，现在再选一次就会产生重复。因此跳过。

4. 详细步骤

   • 步骤1：对数组 nums 进行排序。
   • 步骤2：定义一个结果列表 res 存储所有排列，一个临时列表 path 存储当前排列，一个布尔数组 used 标记每个数字是否被使用。
   • 步骤3：编写回溯函数 backtrack：
     • 如果 path 的长度等于 nums 的长度，说明已经形成一个排列，将其加入 res。
     • 否则，遍历数组中的每个数字：
       • 如果当前数字已被使用，跳过。
       • 如果当前数字与前一个数字相同，且前一个数字未被使用，跳过（剪枝）。
       • 选择当前数字：标记为已使用，加入 path。
       • 递归调用 backtrack 处理下一个位置。
       • 回溯：撤销选择，标记当前数字为未使用，从 path 中移除。
   • 步骤4：调用 backtrack 并返回 res。

5. 示例演示

   • 以 nums = [1,1,2] 为例：
     • 排序后数组为 [1,1,2]。
     • 第一个位置：先选第一个1，递归下去会生成 [1,1,2] 和 [1,2,1]。
     • 回溯到第一个位置，选第二个1时，发现前一个1（即第一个1）未被使用（因为已经回溯撤销），且值相同，因此跳过，避免重复。
     • 然后选2，生成 [2,1,1]。

6. 复杂度分析

   • 时间复杂度：O(n * n!)，最坏情况下没有重复数字，需要生成 n! 个排列，每个排列生成需要 O(n) 时间。
   • 空间复杂度：O(n)，用于递归栈、used 数组和 path 列表。

通过以上步骤，我们可以系统地生成所有不重复的全排列。