leetcode 子集深搜

Dear 丶 2023-08-17 15:43 114阅读 0赞

## 一(每一个数选或不选 ##

> 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

> 说明：解集不能包含重复的子集。

> 示例:

> 输入: nums = \[1,2,3\]  
> 输出:  
> \[  
> \[3\],  
> \[1\],  
> \[2\],  
> \[1,2,3\],  
> \[1,3\],  
> \[2,3\],  
> \[1,2\],  
> \[\]\]

> 来源：力扣（LeetCode）  
> 链接：[https://leetcode-cn.com/problems/subsets][https_leetcode-cn.com_problems_subsets]

class Solution {
    public:
        vector<vector<int>> ans;
        vector<int> now;
        vector<vector<int>> subsets(vector<int>& nums) {
            dfs(nums,0);
            return ans;
        }
        void dfs(vector<int>& nums,int u)
        {
            if(u==nums.size()){
                ans.push_back(now);
                return;
            }
            //选
            now.push_back(nums[u]);
            dfs(nums,u+1);
            now.pop_back();
            dfs(nums,u+1);
        }
    };

# 二(每一个数选零到k个 #

> 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

> 说明：解集不能包含重复的子集。

> 示例:

> 输入: \[1,2,2\]  
> 输出:  
> \[  
> \[2\],  
> \[1\],  
> \[1,2,2\],  
> \[2,2\],  
> \[1,2\],  
> \[\]\]

> 来源：力扣（LeetCode）  
> 链接：[https://leetcode-cn.com/problems/subsets-ii][https_leetcode-cn.com_problems_subsets-ii]

class Solution {
    public:
        vector<vector<int>> ans;
        vector<int> now;
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            dfs(nums,0);
            
            return ans;
        }
        void dfs(vector<int>& nums,int u)
        {
            if(u==nums.size()){
                ans.push_back(now);
                return;
            }
            int k=u;
            while(k<nums.size()&&nums[k]==nums[u])k++;
            //不选
            dfs(nums,k);
            //选K个
            for(int i=u;i<k;++i){
                now.push_back(nums[i]);
                dfs(nums,k);
            }
            //恢复
            for(int i=u;i<k;++i)now.pop_back();
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11358218.html

[https_leetcode-cn.com_problems_subsets]: https://leetcode-cn.com/problems/subsets
[https_leetcode-cn.com_problems_subsets-ii]: https://leetcode-cn.com/problems/subsets-ii