78子集

dfs

dfs1:

和全排列的区别就是对于当前考察的索引i，全排列如果不取i，之后还要取i，所以需要一个visited数组用来记录。对于子集问题如果不取i，之后也不必再取i。

单纯递归回溯

class Solution {

public:

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

        vector<int> cur;

        vector<vector<int>>res;

        dfs(res,cur,nums,0);

        return res;

    }

    void dfs(vector<vector<int>>&res,vector<int>&cur,vector<int>&nums,int nex){

        res.push_back(cur);

        for(int i=nex;i<nums.size();++i){

            cur.push_back(nums[i]);

            dfs(res,cur,nums,i+1);

            cur.pop_back();

        }

    }

};

dfs2:类似树的递归遍历，一个dfs函数里有两个dfs递归子函数，一个是含当前数字的子递归，一个是不含当前数字的子递归。

class Solution {

public:

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

        vector<int>cur;

        vector<vector<int>>res;

        dfs(res,cur,nums,0);

        return res;

    }

    void dfs(vector<vector<int>>&res,vector<int>&cur,vector<int>&nums,int nex){

        if(nex>=nums.size()){

            res.push_back(cur);

            return;

        }

        cur.push_back(nums[nex]);

        dfs(res,cur,nums,nex+1);

        cur.pop_back();

        dfs(res,cur,nums,nex+1);

    }

};

位运算

因为所以数字都不一一样，每个数字都有两种可能，一个取一个不取。假设一共n个元素，则一共有2的n次方个子集，其中每个子集都对应一个小于2的n次方的数。如n==4，1001对应首尾数字取，中间两个数字不取

class Solution {

public:

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

        int n=nums.size();

        vector<vector<int>>res;

        for(int i=0;i<pow(2,n);++i){

            int j=i,k=n-1;

            res.push_back({});

            while(j){

                if(j&1){

                    res.back().push_back(nums[k]);

                }

                j>>=1;

                --k;

            }

        }

        return res;

    }

};

循环

空生空+【1】，空加【1】生空+【1】加【2】加【1，2】。

即1生2，2生4，4生8。。。。

class Solution {

public:

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

        vector<vector<int>>res={{}};

        for(const int& num:nums){

            int cur_size=res.size();

            for(int i=0;i<cur_size;++i){

                res.push_back(res[i]);

                res.back().push_back(num);

            }

        }

        return res;

    }

};

90 子集2

循环

class Solution {

public:

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

        vector<vector<int>>res={{}};

        unordered_map<int,int> mp;

        for(int num:nums){

            mp[num]+=1;

        }

        for(const auto& pai:mp){

            int cur_size=res.size();

            for(int i=0;i<cur_size;++i){

                res.push_back(res[i]);

                for(int j=0;j<pai.second;++j){

                    res.back().push_back(pai.first);

                    res.push_back(res.back());

                }

                res.pop_back();

            }

        }

        return res;

    }

};

dfs

class Solution {

public:

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

        sort(nums.begin(),nums.end());

        vector<vector<int>> res;

        vector<int>cur;

        dfs(res,nums,cur,0);

        return res;

    }

    void dfs(vector<vector<int>>&res,vector<int>&nums,vector<int>&cur,int nex){

        res.push_back(cur);

        for(int i=nex;i<nums.size();++i){

            while(i-1>=nex and i<nums.size() and nums[i]==nums[i-1]){

                ++i;

            }

            if(i>=nums.size()){return;}

            cur.push_back(nums[i]);

            dfs(res,nums,cur,i+1);

            cur.pop_back();

        }

    }

};

巴特西

leetcode78.子集➕90.子集2

78子集

dfs

位运算

循环

90 子集2

循环

dfs

最新文章

热门文章