0047.全排列 II

难度：🟡 中等

标签：数组、回溯

链接：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]]

解题思路

核心思想

本题是“全排列”问题的进阶版，其核心挑战在于输入的数组中可能包含重复数字，而最终结果要求返回所有 不重复的 全排列。这就要求我们在生成排列的过程中，必须有一套去重机制。

思路选择

排序 + 回溯法 是解决此问题的标准最优思路。

• 排序：首先对输入的数组 nums 进行排序。这是去重逻辑能够生效的前提。排序后，所有相同的数字都会被聚集在一起。

• 回溯：我们使用回溯法来探索所有可能的排列。为了避免重复，我们需要在做选择时进行“剪枝”。

• 剪枝逻辑：当我们在遍历选择列表时，如果发现当前数字 nums[i] 与前一个数字 nums[i-1] 相同，并且 前一个数字 nums[i-1] 在当前路径中还没有被使用（!isUsed[i-1]），那么我们就应该跳过当前数字 nums[i]。

  • 这个剪枝的精髓在于，它规定了对于重复的数字，我们必须按照它们在排序后数组中的顺序来选择。例如，对于 [1, 1', 2]，我们只允许先选 1 再选 1' 的路径，而剪掉了先选 1' 再选 1 的路径，从而避免了产生重复的排列。

关键步骤

1. 排序：对 nums 数组进行升序排序。

2. 初始化：创建一个 isUsed 布尔数组，用于记录每个索引的数字是否在当前路径中被使用。

3. 定义回溯函数：创建一个递归函数，例如 backtrack(path, isUsed)。

   • path: 当前正在构建的排列。

   • isUsed: 记录数字使用情况的布尔数组。

4. 设置终止条件：当 path 的长度等于 nums 的长度时，说明找到了一个完整的排列，将其副本加入结果集。

5. 循环与剪枝： a. 遍历 nums 数组。 b. 剪枝：如果当前数字已被使用 (isUsed[i])，或者当前数字与前一个相同且前一个未被使用 (i > 0 && nums[i] === nums[i - 1] && !isUsed[i - 1])，则跳过。 c. 做出选择：将 nums[i] 推入 path，并标记 isUsed[i] = true。 d. 进入下一层决策：递归调用回溯函数。 e. 撤销选择：path.pop()，并重置 isUsed[i] = false。

代码实现

var backTracking = function (choices, path, results, isUsed) {
    if (path.length === choices.length) {
        results.push([...path]);
        return;
    }

    for (let i = 0; i < choices.length; i++) {
        // 关键的剪枝去重逻辑，完全正确
        if (isUsed[i] || (i > 0 && choices[i] === choices[i - 1] && !isUsed[i - 1])) continue;

        path.push(choices[i]);
        isUsed[i] = true;
        backTracking(choices, path, results, isUsed);
        path.pop();
        isUsed[i] = false;
    }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
    // 排序是去重的前提
    nums.sort((a, b) => a - b);
    let results = [];
    let isUsed = new Array(nums.length).fill(false);
    backTracking(nums, [], results, isUsed);
    return results;
};

复杂度分析

• 时间复杂度：O(n × n!) 在最坏的情况下（所有元素都不同），我们需要生成 n! 个排列，每个排列的复制需要 O(n) 的时间。

• 空间复杂度：O(n) 不考虑存储结果的数组，空间复杂度主要由递归调用栈的深度（n）和 used 数组（n）决定。

相关题目

• 0046.全排列

• 0078.子集

• 0090.子集 II

总结

本题是回溯算法中处理重复元素的经典案例。其核心在于“排序”和“剪枝”的结合。通过 if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) 这一行关键代码，我们为重复的元素规定了固定的选取顺序，从而优雅地避免了生成重复的排列。