牛客题霸 [ 集合的所有子集] C++题解/答案

题目描述

现在有一个没有重复元素的整数集合S,求S的所有子集
注意:
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素

题解:

先sort一下,然后通过回溯实现选与不选

代码:

class Solution {
   
public:
    vector<vector<int> > subsets(vector<int> &S) 
	{
   
        vector<vector<int>> sum;
        vector<int> a;
        sort(S.begin(), S.end());
        helper(S, sum, a, 0);
        return sum;
    }
               
    void helper(vector<int>& nums, vector<vector<int>>& sum, vector<int> a, int pos)
	{
   
        if(pos == nums.size())
		{
   
            sum.push_back(a);
        }
		else
		{
   
            helper(nums, sum, a, pos+1); 
            a.push_back(nums[pos]);
            helper(nums, sum, a, pos+1);
        }
    }
};