枚举算法

结题步骤

采用枚举算法解题的一般思路如下：

1. 确定枚举对象、枚举范围和判断条件，并判断条件设立的正确性。
2. 一一枚举可能的情况，并验证是否是问题的解。
3. 考虑提高枚举算法的效率。

提高算法效率方法

1. 抓住问题状态的本质，尽可能缩小问题状态空间的大小。
2. 加强约束条件，缩小枚举范围。
3. 根据某些问题特有的性质，例如对称性等，避免对本质相同的状态重复求解。

递归常见的三类枚举方式是：指数型枚举、排列型枚举、组合型枚举。

指数型枚举

从 1∼n 这 n个整数中随机选取任意多个，输出所有可能的选择方案。
由于每个数都存在选与不选两种状态，所以总共会有2^n 种情况
选与不选可以使用dfs来递归表示
因此递归函数中会用到两个dfs()函数分别表示选与不选

#include <iostream>
using namespace std;

int n;
int st[20]; //结果数组

void dfs(int u){
    if(u > n){
        for(int i=1;i<=n;i++){
            if(st[i] == 1) 
                cout << i << ' ';
        }
        cout << endl;
        return;
    }
    st[u] = 0;
    dfs(u+1);
    
    st[u] = 1;
    dfs(u+1);
}

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

排列型枚举

可以使用stl函数 next_permutation

//时间复杂度 N!
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 110;
int a[N],n;

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        a[i] = i;
    }
    do{
        for(int i=1;i<=n;i++){
            cout << a[i] << ' ';
        }
        printf("\n");
    }while(next_permutation(a+1,a+1+n));
}

组合型枚举

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

可以使用stl函数 prev_permutation

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

const int N=50;
int n, k;
int a[N];

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= k; i++) a[i]=1;
    
    do{
        for(int i = 1; i <= n; i++) if(a[i]) cout<< i <<' ';
        cout << endl;
    }while(prev_permutation(a+1, a+1+n));
    
    return 0;
}