LeetCode 0078 - Subsets
# Hints
DFS
二进制枚举
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a set of distinct integers, , return all possible subsets (the power set).
Note:
The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
# 题意
给定一个大小为 的不可重复集合,求出其所有子集。
# 题解
水题,直接 DFS 暴力枚举所有子集即可。我们在这里提供两种 DFS 的写法,因为后继题目 LeetCode 0090 仅与其中第二种写法有关联。
亦可用二进制枚举解决,因为题目要求把所有子集都储存下来,且所求目标无法剪枝,因此 DFS 的时间复杂度不会比二进制枚举更好,两者效率几乎没有任何区别。
# AC代码(DFS)
class Solution {
public:
vector<vector<int>> subsets(vector<int> & nums) {
// DFS
vector<vector<int>> res;
vector<int> vec;
dfs(0, vec, res, nums);
// 返回
return res;
}
// 深度优先搜索
void dfs(int depth, vector<int> & vec, vector<vector<int>> & res, const vector<int> & nums) {
// 递归终止
if (depth == nums.size()) {
res.push_back(vec);
return;
}
// 递归
vec.push_back(nums[depth]);
dfs(depth + 1, vec, res, nums);
vec.pop_back();
dfs(depth + 1, vec, res, nums);
}
};
class Solution {
public:
vector<vector<int>> subsets(vector<int> & nums) {
// DFS
vector<vector<int>> res;
vector<int> vec;
dfs(0, vec, res, nums);
// 返回
return res;
}
// 深度优先搜索
void dfs(int start, vector<int> & vec, vector<vector<int>> & res, const vector<int> & nums) {
// 更新答案
res.push_back(vec);
// 递归
for (int i = start; i < nums.size(); i ++) {
vec.push_back(nums[i]);
dfs(i + 1, vec, res, nums);
vec.pop_back();
}
}
};
# AC代码(二进制枚举)
class Solution {
public:
vector<vector<int>> subsets(vector<int> & nums) {
// 初始化
int n = nums.size();
vector<vector<int>> res;
// 暴力枚举
vector<int> vec;
for (int status = 0; status < (1 << n); status ++) {
for (int i = 0; i < n; i ++) {
if ((status >> i) & 1) {
vec.push_back(nums[i]);
}
}
res.push_back(vec);
vec.clear();
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01