递归

2.1递归实现指数型枚举

原题链接

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

//递归写法一：vector存
#include<iostream>
#include<vector>

using namespace std;

vector<int>chosen;

int n;

void dfs(int x)
{
    if(x==n+1)//递归边界
    {
        for(int i=0;i<chosen.size();i++)
            printf("%d ",chosen[i]);
        cout<<endl;
        return ;
    }
    
    dfs(x+1);//不选
    
    chosen.push_back(x);
    dfs(x+1);//选
    chosen.pop_back();//回溯还原现场
    
}

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

//递归写法二：用一个book数组记录
#include<iostream>

using namespace std;

int book[20];
int n;

void dfs(int x)
{
    if(x==n+1)
    {
        for(int i=1;i<=n;i++)
        {
            if(book[i]==1)
                cout<<i<<' ';
        }
        cout<<endl;
        return ;
    }
    book[x]=1;//选
    dfs(x+1);
    
    book[x]=0;//不选
    dfs(x+1);
}

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

//递归写法三：状态压缩递归
#include <iostream>

using namespace std;

int n;

void dfs(int x,int state)//x表第几位，state表选还是不选
{
    if(x==n)//0~n-1位
    {
        for(int i=0;i<n;i++)
            if(state>>i&1)//检查state的0~n-1位是否为1
                cout<<i+1<<' ';//第0位数表示1，第一位数表示2.......
        cout<<endl;
        return ;
    }
    dfs(x+1,state);//不选
    dfs(x+1,state|1<<x);//第x位置为1
}

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

---

2.2递归实现组合型枚举

原题链接

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

#include<iostream>
#include<vector>


using namespace std;

vector<int>st;
int n,m;

void dfs(int x)
{
    if(st.size()>m||st.size()+(n-x+1)<m)//如果已经选择了超过m个数，或者即使再选上剩余的所有数也不能够m个
        return ;
    if(x==n+1)
    {
        for(int i=0;i<st.size();i++)
            printf("%d ",st[i]);
        cout<<endl;
        return ;
    }
    
    st.push_back(x);
    dfs(x+1);
    st.pop_back();
    
    dfs(x+1);
}


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

---

2.3递归实现排列型枚举

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

原题链接

#include<iostream>

using namespace std;

int book[10];
int a[10];
int n;

void dfs(int x)
{
    if(x==n+1)
    {
        for(int i=1;i<=n;i++)
            printf("%d ",a[i]);
        cout<<endl;
        return ;
    }
    //填数
    for(int i=1;i<=n;i++)
    {
        if(book[i]==1)continue;
        a[x]=i;
        book[i]=1;
        dfs(x+1);
        book[i]=0;//回溯
    }
}

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