题目描述

给定n,对于集合{1~n}输出集合所有的子集(空集+非空真子集+原集合)

输入样例

3

输入样例

3
2
2 3
1
1 3
1 2
1 2 3

算法1

(暴力枚举) $O(2^n)$

不管是暴力搜索还是动态规划，其中都有两个最基本的概念，即状态和状态转移
何为状态？
对于本题来说，状态就是我已经对于前x个数进行了抉择及其所得到的结果
比如：我对前2个数已经做出了抉择，并且选择第1个数放入子集，第2个数不放入子集，
那么当前状态就可以表示为（3，01）,x=3表示将要做决定的数，显然如果x>n说明已经对所有的数做完了抉择，即当前状态非法，应当输出答案。
何为状态转移？
状态转移即为当前状态往下一个状态变换的逻辑。比如(3,01)可以将3放入子集中得到(4,101),也可以跳过3得到(4,001)

C++ 代码

/*
    Name:AcWing 92. 递归实现指数型枚举
    Author:wyz
    Date:2019/4/2 10:27:42
    Note:
    1.给定集合{1~n}输出集合所有的子集(空集+非空真子集+原集合) 
*/

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
int n;
void dfs(int cur,int station){ 
    //为了便于理解，这里写法与yxc不同
    //cur表示当前要对cur进行选择放入说着不放入
    //station表示对于所有小于cur的数的抉择情况(放入或者不放入)
    //由于cur是不断累加的，总是小数先放入，所以必然升序 
    if(cur>n){//已经挑完了所有的数，结束递归 
        int count=0;//表示第x个数字 
        while(station){
            count++;
            if(station&1)cout<<count<<" ";//如果末位是1，说明当前子集包含该数，并输出 
            station>>=1;//遍历下一位 
        }
        cout<<endl;
        return;
    }
    dfs(cur+1,station);//该集合不包含cur
    dfs(cur+1,station | 1 << (cur-1) );//该集合包含cur
    //因为每次都是选择不放入，所以输出的第一行总是空行，即空集 
    return; 

}
int main(){
    cin>>n;
    dfs(1,0);//从1~n以此进行选择，此时表示对1进行选择，并且当前的状况是集合为空
    return 0;
}