47. 全排列 II

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

回溯-排序-记忆数组+记忆变量剪枝。

利用prevNum变量记录之前树枝上元素的值。排序+used数组去重。

当然，关于排列去重，也有读者提出别的剪枝思路：

class Solution {
    List<List<Integer>> res = new LinkedList<>(); // 结果列表
    LinkedList<Integer> track = new LinkedList<>(); // 用于存储当前的排列内容
    boolean[] used; // 标记数组，用来记录nums中的元素是否已经被使用

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 先对数组进行排序，这样相同的数字就会被排列在一起，便于后续剪枝
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backtrack(nums, track);
        return res;
    }

    void backtrack(int[] nums, LinkedList<Integer> track) {
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }

        // 利用prevNum变量记录之前树枝上元素的值
        // 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值
        // used是全局记忆数组，prevNum是每层递归中的记忆变量。
        // 注意used[i]是避免选中同一个元素，它限制的是索引，我们可以选择索引不同但值相同的元素。
        // 可重不可复选的组合问题（491非递减子序列）中的记忆数组限制的是元素的值，例如[7,7]，选了7之后，本轮以后就不能选7了。
        int prevNum = -666;
        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择。不能复选同一个数。针对同一个数。
            if (used[i]) { // 纵向比较进行剪枝
                continue; // 如果nums[i]已经在本路径中被使用过，则跳过
            }
            // 因为数组中有重复元素，所以需要横向比较进行剪枝，以避免产生重复的排列。used是纵向的，即跨递归的，prevNum是横向的。
            // 注意prevNum是每层递归中的变量，不会跨递归，
            // 因此prevNum是本轮递归中的前一个数，即横向的数，不是track中的上一个选择。
            // prevNum只是单纯为了避免出现重复的结果，类似路径压缩，used数组才是为了避免复选。
            // 针对多个数的顺序。
            if (nums[i] == prevNum) {
                continue;
            }
            // 或者
            // 如果当前元素与前一个元素相同且前一个元素未被使用，跳过以避免重复排列。注意一定要有!used[i - 1]
            // prevNum是横向的上一个数，nums[i-1]可能是纵向的上一个数，也可能是横向的，只有未被使用的才是横向的上一个数。组合问题中不需要加!used[i-1]。
            //if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            //    continue;
            //}

            track.add(nums[i]);
            used[i] = true;
            // 记录这条树枝上的值。注意它不能回溯，因为下一轮for循环要用它本轮的值。
            prevNum = nums[i];
            backtrack(nums, track);
            track.removeLast();
            used[i] = false;
        }
    }
}

回溯-排序-记忆数组-可重不可复选排列。

结束条件：当前排列的长度等于nums的长度，因为排列的长度是一样的。 因为不可复选，所以要用used数组剪枝。因为元素可重且不可复选，所以要排序+（i > 0 && nums[i] == nums[i - 1] && !used[i - 1]）剪枝。

可重不可复选排列

在for循环里面使用记忆数组检查是否重复。

class Solution {
    List<List<Integer>> res = new LinkedList<>(); // 结果列表
    List<Integer> track = new LinkedList<>(); // 用于存储当前的排列内容
    boolean[] used; // 标记数组，用来记录nums中的元素是否已经被使用

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 先对数组进行排序，这样相同的数字就会被排列在一起，便于后续剪枝
        Arrays.sort(nums);
        used = new boolean[nums.length];
        
        backtrack(nums);
        return res;
    }

    void backtrack(int[] nums) {
        // 如果当前排列的长度等于nums的长度，说明找到了一个完整的排列。排列的长度是一样的。
        if (track.size() == nums.length) {
            res.add(new LinkedList(track)); // 将当前排列添加到结果列表中
            return;
        }

        // 从头开始遍历
        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择。不能复选同一个数。针对同一个数。
            if (used[i]) { // 纵向比较进行剪枝
                continue; // 如果nums[i]已经在本路径中被使用过，则跳过
            }
            // 因为数组中有重复元素，所以需要横向比较进行剪枝，以避免产生重复的排列。used是纵向的，即跨递归的，prevNum是横向的。
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                // 如果当前数字和前一个数字相同，且前一个数字还未被使用过，则跳过
                // 这是因为这种情况会产生和前一个数字相同的排列，导致产生相同的排列
                continue;
            }
            
            track.add(nums[i]); // 将nums[i]添加到当前排列中
            used[i] = true; // 标记nums[i]已经被使用
            backtrack(nums); // 递归调用，继续填充排列的下一个数字
            track.removeLast(); // 回溯，从当前排列中移除nums[i]
            used[i] = false; // 取消对nums[i]的使用标记
        }
    }
}

复杂度分析

• 时间复杂度： $O(n \times n !)$ ，其中 $n$ 为序列的长度。 算法的复杂度首先受 backtrack 的调用次数制约， backtrack 的调用次数为 $\sum_{k=1}^n P(n, k)$ 次，其中 $P(n, k)=\frac{n !}{(n-k) !}=n(n-1) \ldots(n-k+1)$ ，该式被称作 $n$ 的 $k$-排列，或者部分排列。而 $\sum_{k=1}^n P(n, k)=n !+\frac{n !}{1 !}+\frac{n !}{2 !}+\frac{n !}{3 !}+\ldots+\frac{n !}{(n-1) !}<2 n !+\frac{n !}{2}+\frac{n !}{2^2}+\frac{n !}{2^{n-2}}<3 n !$。这说明 backtrack 的调用次数是 $O(n !)$ 的。 而对于 backtrack 调用的每个叶结点 (最坏情况下没有重复数字共 $n !$ 个)，我们需要将当前答案使用 $O(n)$ 的时间复制到答案数组中，相乘得时间复杂度为 $O(n \times n !)$ 。

因此时间复杂度为 $O(n \times n !)$ 。

• 空间复杂度： $O(n)$ 。我们需要 $O(n)$ 的标记数组，同时在递归的时候栈深度会达到 $O(n)$ ，因此总空间复杂度为 $O(n+n)=O(2 n)=O(n)$ 。

在分析这段代码的时间和空间复杂度之前，我们需要了解代码的工作机制。该代码使用回溯法生成所有不重复的排列。为了避免重复排列，先对数组排序，并在递归过程中使用剪枝技术。

时间复杂度

1. 排列生成：

   • 对于一个长度为 (n) 的数组，可能的排列数最多为 (n!)（阶乘）。
   • 由于存在重复元素，生成的排列数会小于 (n!)。
   • 假设数组中有 (k) 个重复元素，则不重复排列的数目由 $(\frac{n!}{k_1! \times k_2! \times \cdots \times k_m!})$ 给出，其中 ($k_i$) 是每个不同重复元素的个数。

2. 递归搜索：

   • 每次递归调用都可能需要进行 (O(n)) 次的 for 循环操作以复制答案数组。
   • 因此，在最坏情况下（即无重复元素时），时间复杂度近似为 (O(n \times n!))。

空间复杂度

1. 递归栈：

   • 递归深度最多为 (n)，因此递归调用栈的空间复杂度为 (O(n))。

2. 辅助数据结构：

   • used 数组和 track 链表用于存储中间状态，都是 (O(n)) 的空间。
   • 结果存储在 res 中，其空间复杂度为 (O(n \times n!))。

3. 总体空间复杂度：

   • 综合考虑递归栈和结果存储，空间复杂度为 (O(n \times n!))。