枚举子集

题目 递归实现指数型枚举

思路分析

每个位置不外乎是选还是不选 这可以联想使用二进制的01来表示状态

可以用二进制枚举子集做二进制枚举子集

二进制的方式虽然更容易理解些 但是效率方面会比较低

历年几个题都是 当时想到了用二进制枚举的方式 但是因为效率过低而暴力不出来 所以这类问题还是选择用dfs求解吧 因为dfs可以剪去一些没用的枝 从而较大地提高效率 适用性也更高 因为有时候每个位能考虑的情况会更多而不只是选与不选两种情况

dfs实质也就是递归

代码实现

81ms

#include<bits/stdc++.h>
using namespace std;

const int N=16;
int st[N];//状态，记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它
int n;

void dfs(int u){
    if(u>n){
        for(int i=1;i<=n;i++)
            if(st[i]==1)
                cout<<i<<" ";
        cout<<endl;
        return;
    }

    st[u]=2;//分支1 不选
    dfs(u+1);
    st[u]=0;//还原现场

    st[u]=1;//选
    dfs(u+1);
    st[u]=0;//还原
}

int main()
{
    cin>>n;
    dfs(1);
    return 0;
}

138ms 不再推荐二进制枚举的方式

#include <bits/stdc++.h>
using namespace std;

// 输出所有可能的选择方案
vector<vector<int>> subsets(int n) {
    vector<vector<int>> ans;
    // 从空集开始，到所有元素都选中的集合结束，共2^n种可能
    for (int mask = 0; mask < (1 << n); ++mask) {
        vector<int> t;
        // 遍历每个元素，看其是否应该包含在当前子集中
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                // 由于题目中的数是从1开始的，所以这里要加1
                t.push_back(i + 1);
            }
        }
        ans.push_back(t);
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    auto ans = subsets(n);

    // 输出所有子集，每个子集内的数字按升序排列
    for (auto &subset : ans) {
        for (int num : subset) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

同类题型

视频讲解

⬅️ 指数型（每个位置都可以选所有情况） 🏠 00-刷题理模型 ➡️ 火柴棒等式