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

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;
    }
};

运行结果

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