全排列 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. 最直接：沿用 #46 全排列的 DFS + used 回溯——能枚举所有排列，但 nums 有重复时，会产出重复结果，例如 [1,1,2] 会多次得到 [1,1,2]。

2. 重复在哪里？不是「状态」重复，而是「排列结果」重复：两个相同的 1 互换位置，得到的序列一样。需要在搜索树同层剪掉「选相同值但来自不同下标」的等价分支。

3. 关键观察：先 sort(nums)，同一层 DFS 中，若 nums[i] == nums[i-1] 且左边的 nums[i-1] 本轮还没用（not used[i-1]），说明同层已经用「第一个 1」试过这条路，再选「第二个 1」只会重复。

4. 剪枝条件 i > 0 and nums[i] == nums[i-1] and not used[i-1]：保证相同数字按排序后的下标顺序被使用（先选靠前的副本），从而同层只保留一种选法。

5. 终止与回溯不变：len(path)==n 收集答案；否则对每个合法 i：标记 → 追加 → 递归 → 撤销。n ≤ 8，剪枝后规模仍可控。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`nums`	list<int>	定义：输入数组（可能含重复元素）维护：回溯前先 `sort(nums)`，让相同数字相邻更新：排序后才能在同一 DFS 层用「相邻相等」规则剪枝，避免重复排列
`path`	list<int>	定义：当前正在构造的排列前缀维护：每层从未使用的 `nums[i]` 中选一个追加到末尾更新：递归返回后 `pop` 撤销，保证兄弟分支从同一前缀出发
`used`	list<bool>	定义：长度 `n` 的标记数组，`used[i]` 表示 `nums[i]` 是否已在 `path` 中维护：选 `nums[i]` 前置 `used[i]=True`，回溯时恢复 `False` 更新：保证每个下标最多用一次；配合排序实现同层去重
`ans`	list<list<int>>	定义：所有不重复全排列的集合维护：当 `len(path) == n` 时，将 `path[:]` 副本加入更新：每到达一棵 DFS 叶子追加一次
`i`	int	定义：当前层尝试选取的 `nums` 下标维护：`for i in range(n)`，跳过已用及同层重复值更新：若 `nums[i]==nums[i-1]` 且 `used[i-1]` 为假，说明同层已枚举过该值，直接 `continue`

⌨️ 落码步骤

1. 将 nums 排序；初始化 ans、used = [False]*n、空 path

2. 定义 DFS backtrack()：若 len(path) == n，将 path[:] 加入 ans 并返回

3. 遍历 i ∈ [0, n)：若 used[i] 为真则跳过

4. 同层去重：若 i > 0 and nums[i] == nums[i-1] and not used[i-1]，continue

5. 选择 nums[i]：used[i]=True，path.append(nums[i])，递归，再 pop 并 used[i]=False

6. 启动 backtrack()，返回 ans

💻 代码实现

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans: List[List[int]] = []
        n = len(nums)
        used = [False] * n
        path: List[int] = []

        def backtrack() -> None:
            if len(path) == n:
                ans.append(path[:])
                return
            for i in range(n):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return ans

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        vector<int> path;
        vector<bool> used(nums.size(), false);

        function<void()> dfs = [&]() {
            if (path.size() == nums.size()) {
                ans.push_back(path);
                return;
            }
            for (int i = 0; i < (int)nums.size(); i++) {
                if (used[i]) continue;
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
                used[i] = true;
                path.push_back(nums[i]);
                dfs();
                path.pop_back();
                used[i] = false;
            }
        };

        dfs();
        return ans;
    }
};
// 时间 O(n × n!)，空间 O(n)（递归栈 + used，不计输出）

📈 复杂度分析

时间复杂度 O(n × n!)

空间复杂度 O(n)（递归栈 + used，不计输出）

⚠️ 常见坑

❗ 忘记先排序：不排序则 nums[i]==nums[i-1] 剪枝无效，仍会输出重复排列。

❗ 同层去重条件写反：应是 not used[i-1]（左边相同值未用才跳过），写成 used[i-1] 会误剪合法分支、漏解。

❗ 收集答案时必须存 path[:] 副本；回溯后忘记 pop 或恢复 used[i] 会导致脏状态。

🔍 必测边界 Case

Case 1：全相同

nums = [1,1,1] → [[1,1,1]]（只有一种排列）

Case 2：两两重复

nums = [1,1,2,2] → 6 种不重复排列（4!/(2!×2!) = 6）

Case 3：无重复

nums = [1,2,3] → 6 种排列（退化为 #46，剪枝条件不触发）

Case 4：单元素

nums = [0] → [[0]]

Case 5：含负数

nums = [-1,-1,0] → [[-1,-1,0],[-1,0,-1],[0,-1,-1]]（排序后去重逻辑不变）