LeetCode Q78: Subsets *

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

Note:

• Elements in a subset must be in non-descending order.
• 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],
  []
]

Solution 1:

	class Solution {
	public:
	vector<vector<int>> subsets(vector<int>& nums) {
	vector<vector<int> > res;
	vector<int> emptyset;
	res.push_back(emptyset);
	if(nums.empty())
	return res;
	sort(nums.begin(), nums.end());
	int s=nums.size();
	int k=1;
	int n=nums.size();
	while(k<=s){
	int i=0;
	vector<int> p(k, -1);
	while(i>=0){
	p[i]++;
	if(p[i]>n-1){
	i--;
	continue;
	}
	if(i==k-1){
	vector<int> tmp(k, -1);
	for(int j=0; j<p.size(); j++)
	tmp[j]=nums[p[j]];
	res.push_back(tmp);
	continue;
	}
	i++;
	p[i]=p[i-1];
	}
	k++;
	}
	return res;
	}
	};

view raw Q78-1.cpp hosted with ❤ by GitHub

Solution 2

	class Solution {
	public:
	vector<vector<int> > subsets(vector<int> &S) {
	vector<vector<int> > res(1, vector<int>());
	sort(S.begin(), S.end());
	for (int i = 0; i < S.size(); i++) {
	int n = res.size();
	for (int j = 0; j < n; j++) {
	res.push_back(res[j]);
	res.back().push_back(S[i]);
	}
	}
	return res;
	}
	};

view raw Q78-2 hosted with ❤ by GitHub

Solution 3 (recursion)

	class Solution {
	public:
	vector<vector<int> > helper(vector<int>& nums, int s){
	vector<vector<int> > res;
	if(s==0){
	vector<int> r0;
	vector<int> r1;
	r1.push_back(nums[s]);
	res.push_back(r0);
	res.push_back(r1);
	return res;
	}
	vector<vector<int> > res0=helper(nums, s-1);
	for(int i=0; i<res0.size(); ++i){
	vector<int> r=res0[i];
	res.push_back(r);
	r.push_back(nums[s]);
	res.push_back(r);
	}
	return res;
	}
	vector<vector<int> > subsets(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	vector<vector<int> > res;
	res=helper(nums, nums.size()-1);
	return res;
	}
	};

view raw Q78-4.cpp hosted with ❤ by GitHub

Solution 4 (Bit manipulation)

	class Solution {
	public:
	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;
	}
	};

view raw Q78-3.cpp hosted with ❤ by GitHub

Round 2 solution:
Idea is simple, similar to Q77, don't wait until the last to save the result, instead we save intermediate results in every recursion.

	class Solution {
	public:
	void helper(vector<vector<int> >& res, vector<int>& nums, vector<int>& curRes, int idx){
	res.push_back(curRes);
	if(curRes.size()==nums.size())
	return;
	for(int i=idx+1; i<nums.size(); i++){
	curRes.push_back(nums[i]);
	helper(res, nums, curRes, i);
	curRes.pop_back();
	}
	}
	vector<vector<int> > subsets(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	vector<vector<int> > res;
	vector<int> curRes;
	res.push_back(curRes);
	for(int i=0; i<nums.size(); i++){
	curRes.push_back(nums[i]);
	helper(res, nums, curRes, i);
	curRes.pop_back();
	}
	return res;
	}
	};

view raw Q78round2.cpp hosted with ❤ by GitHub