subsets@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

Given a set of distinct integers, S, 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 S = [1,2,3], a solution is:

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

» Solve this problem

如果有仔细看，会发现这题和上面那题长得很像，和permutations也很像。。。对了，它们就是很像。。。同一类型的题，稍微的变体，在recursion的判断条件上改改就好。

	class Solution {
	public:
	void getSubsets(vector<int> &set, int num, vector<int> &visited, vector<int> &sol, vector<vector<int> > &res)
	{
	if(sol.size()==num)
	{
	res.push_back(sol);
	return;
	}
	for(int i=0; i<set.size(); i++)
	{
	if(visited[i]==0)
	{
	if(sol.size()==0||sol.back()<set[i])
	{
	visited[i]=1;
	sol.push_back(set[i]);
	getSubsets(set, num, visited, sol, res);
	visited[i]=0;
	sol.pop_back();
	}
	}
	}
	}
	vector<vector<int> > subsets(vector<int> &S) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<int> sol;
	vector<vector<int> > res;
	if(S.empty()) return res;
	sort(S.begin(), S.end());
	vector<int> visited(S.size(), 0);
	res.push_back(sol);
	for(int i=1; i<=S.size(); i++)
	{
	getSubsets(S, i, visited, sol, res);
	}
	return res;
	}
	};

view raw Subsets hosted with ❤ by GitHub

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

view raw subsets hosted with ❤ by GitHub