078.md

78. Subsets

Solution 1

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

Solution 2

# DFS
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> cur_ans;
        _subsets(nums, 0, cur_ans, ans);
        return ans;
    }

    void _subsets(vector<int>& nums, int ind, vector<int>& cur_ans, vector<vector<int>>& ans) {
        if (ind == nums.size()) {
            ans.push_back(cur_ans);
            return;
        }
        _subsets(nums, ind + 1, cur_ans, ans);
        cur_ans.push_back(nums[ind]);
        _subsets(nums, ind + 1, cur_ans, ans);
        cur_ans.pop_back();
    }
};