[数据结构与算法]leetcode 47. 全排列 II（46题变形）

?
?

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注? 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

给定一个可包含重复数字的序列 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]]

🧡 算法分析

可先看leetcode 46 全排列

此题方法是用dfs + 回溯

这题剪枝的前提需要先排序，排序后所有相等的数全部都靠在一起

另外，在遇到重复元素时，有两种情况：

• 这个数正在被使用，那么下一个位置能够摆上相同的数字
• 这个数刚刚被撤销，如果下一个位置摆上刚才撤销回来的数字，那么递归树必然和撤销前的递归树重复，所以应该剪枝

这题对比46题，主要是要改一下在遇到相同数字时，需要怎么的操作，我们只需要保证遇到相同数时，不重复搜索就行。
下面的代码主要是这一行起作用： if(i && nums[i - 1] == nums[i] && !st[i - 1]) continue;

1. 因为 i-1的位置比i快选择，如果i-1 还没选 且 在选i的时候 就可以直接跳出 说明已经重复选择i位置了
2. 第n趟递归是要在第n个位置选择一个数放置
3. num[i-1]会比nums[i]早被考虑放到当前位置上
4. bool[i-1]=false说明这个数在上一个排列中已经在这个位置放置过了
5. 所以当前位置不应该再放置与nums[i-1]相等的nums[i]

💚 代码实现

class Solution {
public:
    vector<vector<int>> re;
    vector<int> path;
    vector<bool> st;

    vector<vector<int>> permuteUnique(vector<int>& nums) {

        sort(nums.begin(), nums.end());
        st = vector<bool>(nums.size());
        dfs(nums, 0);
        return re;
    }

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

        for(int i = 0; i < nums.size(); i ++)
        {
            if(!st[i])
            {
                // 因为经过了排序，相同的数字在一起，第一个相同的数字跟前一个数字比较一定不同，肯定能进入递归
                if(i && nums[i - 1] == nums[i] && !st[i - 1]) continue;  // 和46题比较多了这一行条件
                path.push_back(nums[i]);
                st[i] = true;
                dfs(nums, u + 1);
                st[i] = false;
                path.pop_back();
            }
        }
    }
};

执行结果：

💙 时间复杂度分析

时间复杂度: O(n * n !)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
?? 评论，你的意见是我进步的财富！