Leetcode典型题解答和分析、归纳和汇总——T78（求子集）

问题描述：求出一个集合的所有子集，并且进行返回

题目解析：

【1】第一种方法我们可以采用遍历的方式来进行求解，首先，假设为空集，然后逐渐加入元素，进行填充，最终当集合里面所有元素遍历完成之后，子集也就全部找出来了。

class Solution{
    public:
    vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res(1);  //初始化res为一个空元素[[]].
    for(int i=0;i<nums.size();i++)
    {
       int cnt=res.size();
       for(int j=0;j<cnt;j++)  //完成复制功能
       {
           vector<int> tmp = res[j];
           tmp.push_back(nums[i]);
           res.push_back(tmp);  //添加新的集合
       }

    }
    return res;
    }
};
           

【2】第二种方法就是采用回溯算法：回溯返回结果的条件是：tmp元素个数小于nums的元素个数。

class Solution{
    public:
    vector<vector<int>> subsets(vector<int>& nums)
    {
        vector<vector<int>> res;  //用来保存结果
        vector<int> tmp;  //用来保存中间满足题意的子集合
        DFS(res,tmp,nums,0);  //调用回溯函数
        return res;
    }

    void DFS(vector<vector<int>>& res, vector<int>& tmp, vector<int>& nums, int level)
    {
        if(tmp.size()<=nums.size())
        {
            res.push_back(tmp);
        }

        for(int i=level; i<nums.size();i++)
        {
            tmp.push_back(nums[i]);
            DFS(res,tmp,nums,i+1);
            tmp.pop_back();
        }
    }
};