递归实现指数型枚举

题目

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

思路

对于第i个数，你可以选择选或者不选，两种情况分开递归；边界条件为判断完第n个数是否选。

代码

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

vector<int> v;
int n;

void dfs(int x)
{
    if(x==n+1)
    {
        for(int i=0;i<v.size();i++)
        cout<<v[i]<<(i==v.size()-1?'\n':' ');
        return ;
    }
    //put
    v.push_back(x);
    dfs(x+1);
    v.pop_back();

    //not put
    dfs(x+1);
}

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

递归实现组合型枚举

题目

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

思路

加一个判断是否能正好选出m的判断就行了，输出条件仍是遍历完n个数，只要能进入输出条件，一定是正好m个

代码

#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int n,m;
void dfs(int x)
{
    if(v.size()>m || v.size()+n-x+1<m) return ;//只比递归实现指数型枚举多了一句 
    if(x==n+1)
    {
        for(int i=0;i<m;i++)
        cout<<v[i]<<(i==m-1?'\n':' ');
        return ;
    }

    //put
    v.push_back(x);
    dfs(x+1);
    v.pop_back();

    //not put
    dfs(x+1);
}

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

    return 0;
}

递归实现排列型枚举

题目

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

思路

加个vis判断某个数是否选了，即多了个n个数的遍历。

代码

#include<bits/stdc++.h>
using namespace std;
int cnt,n;
bool vis[30];
vector<int> v;
void dfs(int x)
{
    if(x==n+1)//x表示已经选了的个数 
    {
        for(int i=0;i<v.size();i++)
        cout<<v[i]<<(i==v.size()-1?'\n':' ');
        return ;
    }

    for(int i=1;i<=n;i++)
    if(!vis[i]) 
    {
        vis[i]=1;
        v.push_back(i);
        dfs(x+1); 
        v.pop_back();
        vis[i]=0;
    }    
}

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