递归实现指数型枚举

1 ~n的指数枚举
1. 选择1 + [2 ~ n]的指数枚举
2. 不选择1 + [2 ~ n]的指数枚举
终止条件 当获取[n+1 ~ n]的指数枚举时

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> chose;
void cal(int x) {
    if(x == n + 1) {
        int flag = 0;
        for(auto &e:chose)
            if(flag == 0) {
                cout << e;
                flag = 1;
            }else cout << " " << e;
        cout << endl;
        return;
    }
    chose.push_back(x);
    cal(x + 1);
    chose.pop_back();
    cal(x + 1);
}
int main() {
    cin >> n;
    cal(1);
}

递归实现组合型枚举

组合型枚举是指数型枚举的子集，长度限制在m
只要输出长度为m的即可，剪枝
if(si + n - x + 1 < m || si > m) return;

#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> chose;
void cal(int x) {
    int si = chose.size();
    if(si + n - x + 1 < m || si > m) return;
    if(x == n + 1) {
        int flag = 0;
        for(auto &e:chose)
            if(flag == 0) {
                cout << e;
                flag = 1;
            }else cout << " " << e;
        cout << endl;
        return;
    }
    chose.push_back(x);
    cal(x + 1);
    chose.pop_back();
    cal(x + 1);
}
int main() {
    cin >> n>> m;
    cal(1);
}

递归实现排列型枚举

1 2 3 4 … n 的有序全排列:
1. 1 + [2 3 4 … n的有序全排列]
2. 2 + [1 2 3 … n的有序全排列]
3. ....

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> pm;
void cal(int x) {
    if(x == n - 1) {
        int flag = 0;
        for(auto &e:pm)
            if(flag == 0) {
                cout << e;
                flag = 1;
            }else cout << " " << e;
        cout << endl;
        return;
    }
    for(int i = x; i < n; ++i) {
        swap(pm[x], pm[i]);
        cal(x + 1);
    }
    for(int i = x; i < n - 1; ++i)
        swap(pm[i], pm[i+1]);
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i)
        pm.push_back(i);
    cal(0);
}