subsets.cpp (752B)
1 class Solution { 2 public: 3 4 // IDEA: 5 // To construct all possible subsets we may either include an element or not. 6 // Since sets are unique (and the problem says as much), we don't need a de-dupe pass. 7 8 vector<vector<int>> recurse(vector<int> base, vector<int>& nums, int count) { 9 if (count >= nums.size()){ 10 return vector<vector<int>> {base}; 11 } 12 13 auto exclude = recurse(base, nums, count + 1); 14 base.push_back(nums[count]); 15 auto include = recurse(base, nums, count + 1); 16 17 exclude.insert(exclude.end(), include.begin(), include.end()); 18 return exclude; 19 } 20 21 vector<vector<int>> subsets(vector<int>& nums) { 22 return recurse(vector<int>{}, nums, 0); 23 } 24 };