02、全排列

哈喽，大家好，我是厨子，今天继续给大家讲一下全排列

https://leetcode.cn/problems/permutations-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

之前说过排列和组合的不同，排列是有顺序的，[1,2,3]和[3,2,1] 是不同的，但是组合的[1,2,3]和[3,2,1] 是一样的，这块有一些区别，下面我们来对题目进行分析

问题难点：去重

与 LeetCode 46 的区别

LeetCode 46 (全排列):
- 数组无重复元素
- 无需去重

LeetCode 47 (全排列 II):
- 数组有重复元素 ⭐
- 需要去重！

例子: nums = [1,1,2]
不去重: [1₁,1₂,2], [1₂,1₁,2], [1₁,2,1₂], [1₂,2,1₁], [2,1₁,1₂], [2,1₂,1₁]
去重后: [1,1,2], [1,2,1], [2,1,1]  (3个)

如何去重？

关键思路:
1. 排序: 让相同元素相邻
2. 同层去重: 相同元素在同一层只选一次

去重条件:
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
    continue;
}

理解:
- i > 0: 不是第一个元素
- nums[i] == nums[i-1]: 和前一个相同
- !used[i-1]: 前一个在同层没被使用

结论: 跳过，避免重复

树层去重 vs 树枝去重

图解说明

nums = [1,1,2]（已排序）

不去重的完整搜索树:
                      []
        ┌─────────┬───┴───┬─────
        1₁        1₂      2
        │         │       │
    ┌───┴──┐   ┌──┴──┐  ┌─┴───┐
    1₂    2   1₁    2   1₁    1₂
    │     │   │     │   │     │
    2     1₂  2     1₁  1₂    1₁

树层去重（同层跳过）:
                      []
        ┌─────────────┴─────────────┐
        1₁ (选)                     2（这里也跳过了 1₂）
        │                           │
    ┌───┴──┐                     ┌──┴──┐
    1₂    2                      1₁    1₂ (跳过)
    │     │                      │
    2    1₂                      1₂

关键:
第一层: 1₁ 和 1₂ 是同层，只选 1₁，跳过 1₂
第二层: 1₁ 已选，1₂ 和 1₁ 不在同层，可以选

used[i-1]=false: 表示 i-1 在同层
used[i-1]=true: 表示 i-1 在树枝上（已使用）

为什么用 !used[i-1]？

逻辑分析:

情况1: used[i-1] = true（前一个已使用）
说明: nums[i-1] 在当前路径上（树枝）
可以: 继续使用 nums[i]
例子: path=[1₁], 可以选 1₂

情况2: used[i-1] = false（前一个未使用）
说明: nums[i-1] 在同一层已经试过了
应该: 跳过 nums[i]，避免重复
例如: 第一层选过 1₁，就不要在第一层选 1₂

代码:
if (!used[i-1]) {
    continue;  // 同层重复，跳过
}

代码实现

核心版本

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();

        // 排序: 去重的前提
        sort(nums.begin(), nums.end());

        vector<bool> used(nums.size(), false);
        backtrack(nums, used);

        return result;
    }

private:
    void backtrack(vector<int>& nums, vector<bool>& used) {
        // 终止条件
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            // 跳过已使用的
            if (used[i]) {
                continue;
            }

            // 去重: 同层跳过重复元素
            // i > 0: 不是第一个
            // nums[i] == nums[i-1]: 和前一个相同
            // !used[i-1]: 前一个在同层未使用
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
                continue;
            }

            // 回溯
            path.push_back(nums[i]);
            used[i] = true;

            backtrack(nums, used);

            path.pop_back();
            used[i] = false;
        }
    }
};