指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
每个数都可选可不选。

//每一个数都可选可不选
#include<iostream>
using namespace std;
const int N=20;
int n;
bool st[N];
void dfs(int u)
{
    if(u>n)
    {
        for(int i=1;i<=n;i++){
            if(st[i])
                printf("%d ",i);
        }
        printf("\n");
        return;
    }
    st[u]=true;
    dfs(u+1);
    st[u]=false;
    dfs(u+1);
}
int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}

排列型枚举

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
再按字典序输出来

//对每一个位置，枚举每一个没有被之前的位置使用过的数
#include<iostream>
using namespace std;
const int N=10;
bool used[N];
int ways[N];
int n;
void dfs(int u){
    if(u>n)
    {
        for(int i=1;i<=n;i++)
            printf("%d ",ways[i]);
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++)  //枚举所有数，看这个数有没有用过，把没用过的数依次放到现在的位置，再递归下去
    {
        if(!used[i])
        {
            used[i]=true;
            ways[u]=i;
            dfs(u+1);
            used[i]=false;  //恢复现场
        }
    }
}
int main(){
    scanf("%d",&n);
    dfs(1);
    return 0;
}

组合型枚举

从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
（字典序输出）

#include<iostream>
using namespace std;
const int N=30;
int n,m;
int ways[N];
void dfs(int u,int start){
    if(u-1+n-start+1<m) return;  //剪枝，这种枚举情况，总数肯定达不到m
    if(u>m)  //递归边界
    {
        for(int i=1;i<=m;i++)
            printf("%d ",ways[i]);
        printf("\n");
        return;
    }
    for(int i=start;i<=n;i++)  //依次枚举start后面的所有的数
    {                          //因为已经知道start是第一个可以枚举的数了，所以它后面的都可以枚举
        ways[u]=i;
        dfs(u+1,i+1);  //当前u已经填上，去考虑填u+1了，然后当前位置放的i，下一个位置得从i+1开始枚举，不然不满足字典序枚举顺序
    }
}
int main(){
    scanf("%d%d",&n,&m);
    dfs(1,1);  //第一个参数：当前枚举的位置，第二个参数：从那个数开始枚举
    return 0;
}

思考步骤

• 根据题目情况找一个例子在纸上画画递归搜索树
• 抽象出其中的递归本质
• 写代码