题目描述

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],
  []
]

Answer 1 : DFS方法

思路解析：求集合的所有子集的问题。题目要求子集中元素非递减排列。因此，首先要对原来的集合排序。

原来的集合中的每一个元素在子集中只有两种状态：要么存在，要么不存在。这样构造子集的过程中每个元素就有两种选择方法，选择、不选择。因此可以构造一个二叉树，例如对例子中集合{1,2,3}构造的二叉树如下{左子树表示选择该层处理的元素，右子树表示不选择}，最后得到的叶子结点就是要求的子集。

subsets

解法一：深度优先搜索法

class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int>> ret;
vector<int> tmpres;
int len = S.size();
if(len == 0) return ret;
sort(S.begin(), S.end());
subsets_helper(S, tmpres, 0, ret);
//reverse(ret.begin(),ret.end());
return ret;
}
void subsets_helper(vector<int>& S, vector<int>& tmpres, int ileaf, vector<vector<int>>& ret)
{
//达到叶子结点，一个集合元素选择结束
if(ileaf == S.size())
{
ret.push_back(tmpres);
return;
}

//选择ileaf元素
tmpres.push_back(S[ileaf]);
subsets_helper(S, tmpres, ileaf + 1, ret);

//不选择ileaf元素，将ileaf pop出来
tmpres.pop_back();
subsets_helper(S, tmpres, ileaf + 1, ret);
}
};

解法二：位操作

对于数组[1,2,3]，可以用一个下标0和1表示是否选择该数字，0表示未选择，1表示选中，那么每一组3个0和1的组合表示一种选择，3位共有8种选择，分别是：
000 对应[]
001 对应[3]
010 对应[2]
011 对应[2,3]
100 …
101
110
111
那么上面为1的位表示数组中该位被选中。

那么只需要遍历0到1<< length中的数，判断每一个数中有哪几位为1，为1的那几位即会构成一个子集中的一个元素。

实现代码：

class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int>> result;
sort(S.begin(),S.end()); //首先排序；
int len=S.size();
for(int i=0;i<1<<len;i++) //里面有n个数，就有2^n个子集合；
{
vector<int> temp;
for(int j=0;j<len;j++)
{
if(i & 1<<j) //i哪几位为1就取S的哪几位；
temp.push_back(S[j]);
}
result.push_back(temp);
}
return result;
}
};

subsets

题目描述

解法二：位操作

相关推荐