当前位置：首页 > news >正文

DFS：带重复项的全排列，程序运行全流程解析

news 2026/6/14 11:02:23

1. 问题描述

给出一组可能包含重复项的数字，返回该组数字的所有排列，结果以字典序升序排列。

示例：

输入：[1,1,2]
返回值：[[1,1,2],[1,2,1],[2,1,1]]

2. 核心逻辑

在处理[1, 1, 2]时，由于含有两个 1，如果套用最基础的 DFS 模板，就会产生大量冗余的重复排列。

例如：

当我们以第一个 1 为开头，可以得到[1, 1, 2]和[1, 2, 1]。
当我们以第二个 1 为开头，又会得到[1, 1, 2]和[1, 2, 1]。

这样得到的结果就含有重复项。

要想去除掉重复项，需要按照下面的逻辑进行处理：

首先将数组升序排列，让相同的数字放在一起。
然后，在递归树的同一层，如果当前的数字和上一个数字相同，且上一个数字已经尝试过了，那么当前这个数字就不应该再作为开头去尝试。

3. 完整C++代码实现

classSolution{public:/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型vector * @return int整型vector<vector<>> */vector<vector<int>>res;boolused[8]={false};vector<int>path;voiddfs(vector<int>&num){if(path.size()==num.size()){res.push_back(path);return;}for(inti=0;i<num.size();i++){if(used[i])continue;//注意这里i>0很关键，我们肯定不会在第一次循环就进行剪枝if(i>0&&num[i]==num[i-1]&&!used[i-1])continue;used[i]=true;path.push_back(num[i]);dfs(num);path.pop_back();used[i]=false;}}vector<vector<int>>permuteUnique(vector<int>&num){//排序是剪枝的前提sort(num.begin(),num.end());dfs(num);returnres;}};

4. 程序运行全过程

假设输入数组已排序为nums = [1, 1, 2]，我们来分析一下 DFS 的完整流程，大家可以对照上面的代码看下面的流程分析：

从根节点出发：

选择nums[0]，此时used = [T, F, F]，push_back之后path = [1]。
进入第二层递归：
- 由于used[0]为true，所以会直接跳过第一轮for循环，选择第二轮for循环的nums[1]，此时used = [T, T, F]，push_back之后path = [1, 1]。
- 然后进入第三层递归：
  - 前两个used都为true，选择nums[2]，此时used = [T, T, T]，push_back之后path = [1, 1, 2]，这是第一个结果。
  - 在尝试进行第四次递归时，此时已经满足了path.size() == num.size()，于是进行回溯。
  - 回到第三层递归，执行pop_back并把used[2]置位false，当前used = [T, T, F]，path = [1, 1]。
  - 此时，for循环达到边界，跳出循环，本次dfs调用结束，进行回溯。
- 回溯到第二层，执行pop_back并把used[1]置位false，当前used = [T, F, F]，path = [1]。
- 然后进行第二层的下一轮for循环，此时选择nums[2]，path = [1, 2]。
  - 然后再进入第三次递归，选择nums[1]，此时，path = [1, 2, 1]。
  - 得到了第二个结果[1, 2, 1]，然后进行回溯。
  - 此时，回溯到第二层之后，第二层递归的for循环也结束了，继续回溯。

程序又回到了根节点：

撤销了num[0]，此时used = [F, F, F]，path = []，进入根节点的第二轮for循环。
准备选择第二个 1 时，触发判断条件nums[1] == nums[0]且used[0] == false，这意味着nums[0]刚刚作为开头已经完整试过了所有可能性，并退回了。
这时执行剪枝，用continue直接跳过第二个 1 。

收尾：