Day 23。
今天两道题分别是 Permutations 和 Permutations II。
这两题是一组非常经典的排列题：

  • 46 是全排列
  • 47 是带重复元素的全排列去重版

所以今天的核心主线非常明确：

回溯生成排列 + 去重控制

今天的关键词：回溯、排列、used 数组、树枝选择、排序、同层去重。

🧠 LeetCode 46 – Permutations

💡 思路总结

这题要求返回数组的所有排列。
看到“所有排列”这种关键词，第一反应基本就是：

回溯

因为排列问题本质上是在做一棵决策树搜索：

  • 第一个位置放哪个数？
  • 第二个位置放哪个数？
  • 第三个位置放哪个数？
  • ……

你的写法非常标准，属于排列题的经典模板：

  • path 记录当前已经选出的排列
  • used 记录哪些元素已经被用过
  • 当 path.size() == nums.size() 时，说明得到一个完整排列

💻 代码实现

class Solution {
public:
    //回溯三件套
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used;

    vector<vector<int>> permute(vector<int>& nums) {
        used.resize(nums.size(),false);
        dfs(nums);
        return result;
    }
    void dfs(vector<int>& nums){
        if(path.size()==nums.size()){
            result.push_back(path);
            return;
        }
        for(int i = 0;i< nums.size();i++){
            if(used[i])continue;
            path.push_back(nums[i]);
            used[i]= true;
            dfs(nums);
            path.pop_back();
            used[i]=false;
        }
    }
};

📌 知识点总结

1️⃣ 排列和组合的区别

这题和前面的组合题不一样，最大的区别在于：

排列里顺序不同，算不同答案

比如：

  • [1,2,3]
  • [1,3,2]

这是两个不同排列。

所以这里不能像组合题那样用 pos 限制从后面选，
而是每一层都要重新从头遍历所有元素，只要这个元素还没用过，就可以选。

2️⃣ used 数组是排列题核心

你这里的：

vector<bool> used;

作用非常关键。

它表示：

  • 当前路径中哪些元素已经被选过了

这样每次递归时，只要看到：

if(used[i]) continue;

就知道这个元素这一条路径里不能再重复使用。

这和组合题非常不一样。
组合题常用 pos，排列题常用 used。

3️⃣ 回溯三件套写得很标准

你这里其实就是非常经典的回溯三步：

选择

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

递归

dfs(nums);

撤销选择

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

这个结构特别值得记熟，因为排列题几乎都是这个框架。

4️⃣ 为什么结束条件是 path.size() == nums.size()

因为排列要求的是：

所有元素都恰好用一次

所以当路径长度已经和原数组长度一样时，就说明当前路径已经构成一个完整排列，可以直接加入答案。

🔥 LeetCode 47 – Permutations II

💡 思路总结

这题和上一题几乎一样，也是求全排列。
但这里数组里可能有重复数字，所以要求：

返回所有不重复的排列

这时候就不能直接照搬上一题了，不然会出现重复答案。
所以这题的关键在于：

  • 先排序
  • 再在回溯时做去重

你的做法就是这题的经典正解。

💻 代码实现

class Solution {
public:
    //还是回溯；但是要去重（加个判断）排序
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        used.resize(nums.size(),false);
        dfs(nums);
        return result;
    }

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

    }
};

📌 知识点总结

1️⃣ 为什么一定要先排序

这一句非常关键：

sort(nums.begin(), nums.end());

只有排序之后，相同元素才会相邻，后面的去重条件才有意义。

如果不排序，你根本没法通过：

nums[i] == nums[i-1]

来判断当前元素是不是和前一个重复。

2️⃣ 这句去重条件是灵魂

if(i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

这句一定要真正理解。

它的意思是：

当前数字和前一个数字相同，而且前一个数字在这一层还没被使用过，那么当前这个数字不能先选。

为什么？

因为如果前一个相同数字都还没用，你现在先用后一个，相当于只是交换了两个相同元素的顺序，最终会生成重复排列。

所以这里本质上是在做：

同层去重

3️⃣ 为什么判断的是 !used[i-1]

这个地方非常关键，也特别容易背混。

  • used[i-1] == false：说明前一个相同元素还没在当前路径中使用，也就是它和当前元素处于“同一层竞争关系”
  • 这时候跳过当前元素，避免同层重复

反过来：

  • 如果 used[i-1] == true
  • 说明前一个相同元素已经在当前路径里用了，当前元素是在更深一层被选到的
  • 这种情况不应该跳过

所以这个判断其实是在区分：

  • 同层重复
  • 同枝合法

4️⃣ 和 LeetCode 46 的关系

这题其实就是上一题的升级版：

题目核心区别
LeetCode 46无重复元素，直接回溯
LeetCode 47有重复元素，需要排序 + 去重

也就是说，这题不是全新模型，而是在 46 的排列回溯模板上，再加一层去重逻辑。

🧩 两题放在一起看

今天这两题特别适合对照着理解：

题目核心思想
LeetCode 46回溯 + used 数组生成全排列
LeetCode 47排序 + 回溯 + used 数组 + 去重

它们其实告诉我们一个很重要的结论：

排列题核心框架很稳定，变化通常只在“要不要去重”。

🧠 今日收获

今天最值得记住的两个模型：

1. 全排列回溯模型

如果题目要求：

  • 所有排列
  • 顺序不同算不同答案

那就优先想：

  • path
  • used
  • 每层从头枚举所有元素

2. 排列去重模型

如果排列题里有重复元素，那就要想到：

  • 先排序
  • 用 used 配合判断
  • 防止同层重复选择相同元素

最经典的条件就是：

if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

这个条件一定值得反复理解。

💬 写给自己的话

Day 23 了。

你现在已经在慢慢碰到很多“成套出现”的题了：

  • 组合 和 组合去重
  • 排列 和 排列去重
  • 普通二分 和 边界二分
  • 普通回溯 和 剪枝回溯

这特别好。
因为真正的刷题提升，不只是会一题，而是你开始看懂：

同一类题，变的到底是哪一部分。

今天这两题就是非常典型的例子。
回溯框架没变，变的是“重复元素怎么处理”。

继续保持这个节奏。
你现在做的，不只是打卡，而是在慢慢建立题型之间的联系。

阿玉，Day 23，继续冲。

—— 刷题第 23 天