78. 子集

两种方法
子集是求组合数。46题 47题是求排列数

第一种循环

class Solution {
public:
   vector<vector<int>> subsets(vector<int>& nums) {
       vector<vector<int>> res;
       res.push_back({});
       for(auto x: nums)
       {
           int len = res.size();
           for(int i = 0; i < len; i++)
           {
               auto tmp = res[i];
               tmp.push_back(x);
               res.push_back(tmp);
           }
       }
       return res;
   }
};

第二次写题

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        res.push_back({});
        for(int i = 0; i < nums.size(); i++)//遍历每一个数字
        {
            int n = res.size();
            for(int j = 0; j < n; j++)
            {
                vector<int> tmp = res[j];
                tmp.push_back(nums[i]);
                res.push_back(tmp);
            }
        }
        return res;
    }
};

第二种dfs

class Solution {
   vector<vector<int>> res;
   vector<int> nums;
   void dfs(long long idx)
   {
       if(idx == nums.size())
           return;
       int len = res.size();
       for(int i = 0; i < len; i++)
       {
           auto tmp = res[i];
           tmp.push_back(nums[idx]);
           res.push_back(tmp);
       }
       dfs(idx + 1);
   }
public:
   vector<vector<int>> subsets(vector<int>& _nums) {
       nums = _nums;
       res.push_back({});
       dfs(0);
       return res;
   }
};

第三次写题

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res = {{}};
        for(int i = 0; i < nums.size(); i++)
        {
            int len = res.size();
            for(int j = 0; j < len; j++)
            {
                auto tmp = res[j];
                tmp.push_back(nums[i]);
                res.push_back(tmp);
            }
        }
        return res;
    }
};