指数型、组合型和排列型枚举

常见的枚举形式和遍历方式

指数型枚举（子集枚举）

// 递归版
#include <iostream>
#include <vector>
using namespace std;

const int N = 1010;
int n, a[N];
vector<int> res;

void dfs (int kth) {
    if (kth == n + 1) {
        for (int i = 0; i < res.size(); ++ i) printf("%d ", res[i]);
        printf("\n");
        return;
    }
    dfs(kth + 1); // 不取 a[kth]

    res.push_back(a[kth]);
    dfs(kth + 1);
    res.pop_back();
}

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    dfs(1);
    return 0;
}

// 循环版
#include <iostream>
#include <vector>
using namespace std;

const int N = 1010;
int n, a[N];

int main () {
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) scanf("%d", &a[i]); // 0-index

    for (int i = 0; i < (1 << n); ++ i) {
        vector<int> res;

        for (int j = 0; j < 32; ++ j)
            if (i & (1 << j))
                res.push_back(a[j]);

        for (int j = 0; j < res.size(); ++ j)
            printf("%d ", res[j]);
        printf("\n");
    }
    return 0;
}

组合型枚举

#include <iostream>
#include <vector>
using namespace std;

const int N = 1010;
int n, a[N], m;
vector<int> res;

void dfs (int kth) {
    // res.size() > m 表示选多了
    // res.size() + (n - kth + 1) < m 表示选少了
    if (res.size() > m || res.size() + (n - kth + 1) < m) return;
    if (kth == n + 1) {
        for (int i = 0; i < res.size(); ++ i) printf("%d ", res[i]);
        printf("\n");
        return;
    }
    dfs(kth + 1);

    res.push_back(a[kth]);
    dfs(kth + 1);
    res.pop_back();
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    dfs(1);
    return 0;
}

排列型枚举

#include <iostream>
#include <vector>
using namespace std;

const int N = 1010;
int n, a[N];
bool mark[20];
vector<int> res;

void dfs (int kth) {
    if (kth == n + 1) {
        for (int i = 0; i < res.size(); ++ i) printf("%d ", res[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; ++ i) {
        if (mark[i] == false) {
            mark[i] = true;
            res.push_back(a[i]);
            dfs(kth + 1);
            mark[i] = false;
            res.pop_back();
        }
    }
}

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    dfs(1);
    return 0;
}