1. 078
2. 算法
http://www.tuicool.com/articles/J3En2e
http://www.tuicool.com/articles/J3En2e
2.1 dfs:O(2^n)
- 求集合的所有子集问题。题目要求子集中元素非递减序排列，因此我们先要对原来的集合进行排序。原集合中每一个元素在子集中有两种状态：要么存在、要么不存在。这样构造子集的过程中每个元素就有两种选择方法：选择、不选择，因此可以构造一颗二叉树，例如对于例子中给的集合[1,2,3]，构造的二叉树如下（左子树表示选择该层处理的元素，右子树不选择），最后得到的叶子节点就是子集：
2.2 位运算：O(2^n)
- 对于n个元素，每个元素要么加入要么不加入，则会得到一个n位的二进制串，n为二进制串可以看做是一个状态或者说一个子集，每个元素与一位一一对应，状态的大小为1<<n( 左移n位). 对于每个状态j，我们通过判断第k位是否为1，为1则将S[k]加入vec，判断结束，将vec加入result即可。
3 代码
3.1 DFS(递归)
class Solution{
public:
vector<vector<int> > subsets(vector<int>& S){
vector<vector<int> > res;
vector<int> out;
sort(S.begin(),S.end());
getSubsets(S,0,out,res);
return res;
}
private:
void getSubsets(vector<int >&S,int pos,vector<int>& out,vector<vector<int> >& res){
res.push_back(out);
for(int i=pos;i<S.size();i++){
out.push_back(S[i]);
getSubsets(S,i+1,out,res);
out.pop_back();
}
}
};
3.2 优化DFS
观察上述搜索树，发现当前层的集合=上一层的集合+上一层集合加上当前元素的集合。那么有此规律，我们完全就可以省去递归开销。
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > res(1); //初始有一个空集
vector<int> tmp;
sort(S.begin(),S.end());
for(int i=0;i<S.size();i++){
int n=res.size();
for(int j=0;j<n;j++){
tmp=res[j];
tmp.push_back(S[i]);
res.push_back(tmp);
}
}
return res;
}
};
3.3 位运算
//位处理
class Solution{
public:
vector<vector<int> > subsets(vector<int>& S){
vector<vector<int> > res;
sort(S.begin(),S.end());
int max=1<<S.size();
for(int k=0;k<max;++k){
vector<int> out=convertIntToSet(S,k);
res.push_back(out);
}
return res;
}
private:
vector<int> convertIntToSet(vector<int>& S,int k){
vector<int> sub;
int idx=0;
for(int i=k;i>0;i>>=1){
if((i&1)==1){
sub.push_back(S[idx]);
}
++idx;
}
return sub;
}
};