Subsets

这是一道求子集的题目，题目链接，一开始用了三重循环，复杂度极高，不过还是没有超时。代码如下

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        set<set<int>> ans_s;
        ans_s.insert(set<int>({}));
        for(int i = 0; i <= nums.size(); i++){
            auto tmp = ans_s;
            for(auto num : nums){
                for(auto s_s : tmp){
                    s_s.insert(num);
                    ans_s.insert(s_s);
                }
            }
        }

        vector<vector<int>> ans;
        for(auto s : ans_s){
            ans.push_back(vector<int>(s.begin(), s.end()));
        }
        return ans;
    }
};

代码思路就是每次加入一个数字，得到当前的所有子集。直到所有数字都被加入。这中做法使用set来去除重复。
第二种的思路是用回溯的思想，参考了前一道题目的代码。代码如下

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        helper(nums, 0, vector<int>(), ans);
        return ans;
    }
    
    void helper(vector<int> &nums, int pos, vector<int> out, vector<vector<int>> &ans) {
        ans.push_back(out);
        for(int i = pos; i < nums.size(); ++i) {
            out.push_back(nums[i]);
            helper(nums, i+1, out, ans);
            out.pop_back();
        }
    }
};