题目: 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],
[]
]
思路一: 采用深度优先搜索
class Solution
{
private:
vector<vector<int>> result;
int maxDepth;
private:
//深度优先搜索
//depth控制搜索的深度,previous是前一次搜索的结果,orgin是原始集合,start表示在origin中开始索引
void dfs(int depth, vector<int> previous, vector<int> &origin, int start)
{
result.push_back(previous);//将前一次的结果加入最终结果集合
if (depth > maxDepth) return;//如果大于最大深度,则退出
for (int i = start; i < maxDepth; ++i)
{
vector<int> current(previous);
current.push_back(origin[i]);
dfs(depth + 1, current, origin, i + 1);
}
}
public:
vector<vector<int>> subsets(vector<int> &S)
{
maxDepth = int(S.size());
result.clear();
if (0 == maxDepth) return result;
sort(S.begin(), S.end());
vector<int> current;
dfs(0, current, S, 0);
return result;
}
};
思路二: 在网络上看到这样一种思路,觉得很巧妙。对于数组中的一个数:要么存在于子集中,要么不存在。 则有下面的代码:
class Solution
{
private:
vector<vector<int>> result;
int maxDepth;
void dfs(int depth, vector<int> current, vector<int> &origin)
{
if (depth == maxDepth)
{
result.push_back(current);
return;
}
dfs(depth + 1, current, origin);//子集中不存在origin[depth]
current.push_back(origin[depth]);
dfs(depth + 1, current, origin);//子集中存在origin[depth]
}
public:
vector<vector<int>> subsets(vector<int> &S)
{
maxDepth = int(S.size());
result.clear();
if (0 == maxDepth) return result;
sort(S.begin(), S.end());
vector<int> current;
dfs(0, current, S);
return result;
}
};