Leetcode—47.全排列II【中等】

2023-12-21 16:36:59

2023每日刷题(六十六)

Leetcode—47.全排列II

在这里插入图片描述

直接用set实现代码

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        set<vector<int>> ans;
        int n = nums.size();
        vector<int> path(n);
        vector<bool> visited(n);
        function<void(int)> dfs = [&](int i) {
            if(i == n) {
                ans.insert(path);
                return;
            }
            for(int j = 0; j < n; j++) {
                if(!visited[j]) {
                    visited[j] = true;
                    path[i] = nums[j];
                    dfs(i + 1);
                    visited[j] = false;
                }
            }
        };
        dfs(0);
        vector<vector<int>> res;
        for(auto it = ans.begin(); it != ans.end(); it++) {
            res.push_back(*it);
        }
        return res;
    }
};

运行结果

在这里插入图片描述

剪枝算法思想

参考k神的思路
在这里插入图片描述

剪枝+set实现代码

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();
        function<void(int)> dfs = [&](int x) {
            if(x == n - 1) {
                ans.emplace_back(nums);
                return;
            }
            set<int> st;
            for(int i = x; i < n; i++) {
                // 剪枝
                if(st.find(nums[i]) != st.end()) {
                    continue;
                }
                st.insert(nums[i]);
                // 把nums[i]固定在第x位
                swap(nums[i], nums[x]);
                dfs(x + 1);
                swap(nums[i], nums[x]);
            }
        };
        dfs(0);
        return ans;
    }
};

运行结果

在这里插入图片描述

之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!

文章来源:https://blog.csdn.net/qq_44631615/article/details/135130624
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。