递归与排列组合问题

递归实现指数型枚举

题意简化：输出\(1-n\)之间的子集

代码实现

递归实现组合型枚举

#include<iostream>
using namespace std;
int n;
int a[1000005];
int rear;
void dfs(int cur) {
    if(cur == n + 1) {           //如果没有数可操作了
        for(int i = 0 ; i < rear ; ++i) {   //直接输出
            cout << a[i] <<; " ";
        }
        cout << endl;
        return;
    }
    dfs(cur + 1);  //当前的数不选
    a[rear++] = cur;   //当前的数选
    dfs(cur + 1);
    rear--;
}
int main() {
    cin >> n;
    dfs(1);
    return 0;
}

题意简化：输入\(n\)和\(m\)，求\(C_{n}^{m}\)，按字典序输出

代码实现

#include<iostream>
using namespace std;
int n, m;  //n表示数据规模，x表示位数
int x[10005], rear;
void dfs(int cur) {      //cur表示当前的数
    if(rear == m){
        for(int i = 1 ; i &lt;= m ; ++i) {
            cout << x[i] << " ";
        }
        cout << endl;
        return;
    }
    if(cur == n + 1)
        return;              //由于是字典序，所以先将状态转移到选择的，再转移到不选择的
    x[++rear] = cur;  //选择这个数
    dfs(cur + 1);
    x[rear--] = 0;  //不选这个数       
    dfs(cur + 1);    
}
int main() {
    cin >> n >> m;
    dfs(1);
    return 0;
}

递归实现排列型枚举

简化题意：给定一个数\(n\)，输出\(1-n\)之间的排列，按字典序输出

代码实现

#include<iostream>
using namespace std;
int n;  //n表示数据规模
int x[1000005];
bool vis[1000005];
void dfs(int cur) {      //cur表示当前的数
    if(cur == n + 1){
        for(int i = 1 ; i <= n ; ++i) {
            cout << x[i] <<; " ";
        }
        cout &lt;&lt; endl;
        return;
    }
    for(int i = 1 ; i <= n ; ++i) {
        if(vis[i])       //如果访问过
            continue;
        vis[i] = true;
        x[cur] = i;
        dfs(cur + 1);
        vis[i] = false;
    }      
}
int main() {
    cin >> n;
    dfs(1);
    return 0;
}