递归枚举的三种情况
1.指数型枚举 每位都可以取或不取 有2^n种情况
2.组合型枚举 从m个数种选取n个的情况 有cmn 种情况 m!/(n!*(m-n)!)
3.排列型枚举 给n的数进行排列组合 有amn种情况 m!/(m-n)!

statue+(1<<i) 给第i位填1 statue>>i&1取st第i位

指数型枚举：
1.参数u指代枚举到第几个数
2.参数st表示每个数字是否选取
3.每次递归选取或不选取两种情况

#include <iostream>

using namespace std;

int n;

void dfs(int u,int statue){//statue 二进制存储当前状态

    if(u==n){
        for(int i=0;i<n;i++){
            if(statue>>i&1){  //取第i位
                cout<<i+1<<" ";
            }
        }
        cout<<endl;
        return ;
    }
    dfs(u+1,statue);
    dfs(u+1,statue+(1<<u)); //在第u位上填1
}

int main(){

    cin>>n;

    dfs(0,0);

    return 0;
}

组合型枚举：
1.参数u指代已经选取了几个数字
2.参数s指代可选取的范围
3.参数st表示每个数字是否选取
4.每次都是从可选范围内进行枚举

#include <iostream>

using namespace std;

int n,m;
bool st[30];

void dfs(int u,int s,int statue){
    if(u==m){
        for(int i=0;i<n;i++){
            if(statue>>i&1){
                cout<<i+1<<" ";
            }
        }
        cout<<endl;
        return ;
    }

    if(s==n) return ;// 出现 类似 1 5 后面没有数字填的情况

    for(int i=s;i<n;i++){//从当前移动到的位置s开始
        dfs(u+1,i+1,statue+(1<<i));
    }

}

int main(){

    cin>>n>>m;

    dfs(0,0,0);//第一位：已经填的数量 第二位：当前使用到的位置（保证字典序） 第三位：二进制状态 


    return 0;
}

排列型枚举：
1.与组合型相似
2.但是组合型是单个情况内部按字典序排列，而排列型是内部不按字典序排列
3.需要额外的参数来表示顺序 如vector等

#include <iostream>
#include <vector>

using namespace std;

int n;

vector <int> path;

void dfs(int u,int st){//排列型到n时，st均为1，需要用其他变量vector 来表示顺序；
    if(u==n){
        for(auto i:path){
            cout<<i<<" ";
        }
        cout<<endl;
        return ;
    }
    for(int i=0;i<n;i++){
        if(!(st>>i&1)){
            path.push_back(i+1);
            dfs(u+1,st+(1<<i));
            path.pop_back();
        }
    }
}

int main(){

    cin>>n;

    dfs(0,0);//第一位：已经填的数量 第二位：二进制状态


    return 0;
}