枚举子集的3种方式 -- C++描述
时间: 2023-09-19 13:10:03 浏览: 60
以下是C++描述的3种枚举子集的方式:
1. 位运算法
```cpp
for(int i = 0; i < (1 << n); i++) {
for(int j = 0; j < n; j++) {
if(i & (1 << j)) {
// 处理子集中包含 j 的情况
}
}
}
```
2. 递归法
```cpp
void dfs(int cur, vector<int>& subset, int n) {
// 处理子集 subset
for(int i = cur; i <= n; i++) {
subset.push_back(i);
dfs(i + 1, subset, n);
subset.pop_back();
}
}
vector<vector<int>> subsets(int n) {
vector<vector<int>> res;
vector<int> subset;
dfs(1, subset, n);
return res;
}
```
3. 迭代法
```cpp
vector<vector<int>> subsets(int n) {
vector<vector<int>> res{{}};
for(int i = 1; i <= n; i++) {
int size = res.size();
for(int j = 0; j < size; j++) {
res.push_back(res[j]);
res.back().push_back(i);
}
}
return res;
}
```