# Subsets

Oct 20, 2017

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]


vector<vector<int>> subsets(vector<int>& nums) {
vector< vector<int> > ret;
vector<int> vec;
ret.push_back(vec);
subsetsIter(ret,nums,vec,0);
return ret;
}

void subsetsIter(vector< vector<int> > &ret,vector<int> &nums,vector<int> now,int beg) {
//if (now.size() == nums.size()) return ;
now.push_back(-1);
auto rbeg = now.rbegin();
for(int i = beg;i < nums.size();i++) {
*rbeg = nums[i];
ret.push_back(now);
subsetsIter(ret,nums,now,i+1);
}
now.pop_back();
}


vector<vector<int>> subsets(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> subs(1, vector<int>());
for (int i = 0; i < nums.size(); i++) {
int n = subs.size();
for (int j = 0; j < n; j++) {
subs.push_back(subs[j]);
subs.back().push_back(nums[i]);
}
}
return subs;
}

vector<vector<int>> subsets(vector<int>& nums) {
sort(nums.begin(), nums.end());
int num_subset = pow(2, nums.size());
vector<vector<int> > res(num_subset, vector<int>());
for (int i = 0; i < nums.size(); i++)
for (int j = 0; j < num_subset; j++)
if ((j >> i) & 1)
res[j].push_back(nums[i]);
return res;
}

LeetCodeLeetCode

Word Search

Sort Colors