LeetCode刷题--- 全排列 II

?个人主页：元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

?http://t.csdnimg.cn/yUl2I? ?

【C++】? ? ? ? ?

?http://t.csdnimg.cn/6AbpV?

数据结构与算法

?http://t.csdnimg.cn/hKh2l

前言：这个专栏主要讲述递归递归、搜索与回溯算法，所以下面题目主要也是这些算法做的 ?

我讲述题目会把讲解部分分为3个部分：
1、题目解析

2、算法原理思路讲解

3、代码实现

全排列 II

题目链接：?全排列 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

解法

题目解析

给我们可包含重复数字的序列?nums?，按任意顺序?返回所有不重复的全排列

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

算法原理思路讲解????

?

?决策树就是我们后面设计函数的思路

二、设计代码

（1）全局变量

vector<int> path;          // 存储路径
vector<vector<int>> ret; 
bool check[10] = {false};  

• 定义?个?维数组 ret??来存放所有可能的排列
• ?个?维数组 path??来存放每个状态的排列
• ?个?维数组 check?标记元素?

（2）设计递归函数

void dfs(vector<int>& nums, int pos);

• 参数：pos（当前需要填?的位置）；
• 返回值：?；
• 函数作?：查找所有合理的排列并存储在答案列表中

?

?前提：这个数组是有序的

1. 定义?个?维数组 ret??来存放所有可能的排列，?个?维数组 path??来存放每个状态的排列，?个?维数组 check?标记元素，然后从第?个位置开始进?递归；
2. 在每个递归的状态中，我们维护?个步数 pos，表?当前已经处理了?个数字；
3. 递归结束条件：当 pos?等于 nums 数组的?度时，说明我们已经处理完了所有数字，将当前数组存?结果中；
4. 在每个递归状态中，枚举所有下标 i，若这个下标未被标记，并且在它之前的相同元素被标记过， 则使? nums 数组中当前下标的元素：
   1. 将 check[i] 标记为 true；
   2. 将 nums[i] 添加? path?数组末尾；
   3. 对第 pos+1 个位置进?递归；
   4. 将 check[i] 重新赋值为 false，并删除 path?末尾元素表?回溯；
5. 最后，返回 ret

class Solution 
{
    vector<int> path;          // 存储路径
    vector<vector<int>> ret; 
    bool check[10] = {false};  

    void dfs(vector<int>& nums, int pos)
    {
        if (pos == nums.size())
        {
            ret.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] != false))
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums,pos+1);
                path.pop_back();
                check[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        dfs(nums,0);

        return ret;
    }
};