1.指数型枚举

acwing92.递归实现指数型枚举

#include <iostream>

using namespace std;

int n;
bool st[20];

//如果选择要满足条件，则可以加个参数，如4.
void f(int u)
{
    if(u == n+1)
    {
        for(int i = 1; i <= n;i ++)
            if(st[i]) cout << i << " ";
        cout << endl;
        return ;
    }

    //选
    st[u] = true;
    f(u + 1);
    st[u] = false;

    //不选
    f(u + 1);
}

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

2.排列型枚举

acwing94.排列型枚举

#include <iostream>

using namespace std;

int n;
int arr[10];
bool st[10];

void f(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n;i ++)
            cout << arr[i] << " ";
        cout << endl;
        return ;
    }
    for(int i = 1; i <= n; i ++)
    {
        // 因为一个数能用多次，故用st[N];
        if(!st[i])
        {
            st[i] = true;
            //这里u指的是查找树的层数，i是选择
            //有时u可同时表示层数和数组i
            arr[u] = i;
            f(u + 1);
            st[i] = false;
        }
    }
}

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

3.组合型枚举

acwing93.组合型枚举
法一：递归n层，选或不选，选够n个停止

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50;

int n, m;
vector<int> res;

void dfs(int u)
{
    if(u > n + 1) return;
    if(res.size() == m)
    {
        for(int x : res)
            cout << x << " ";
        cout << endl;
        return;
    }

    // 选
    res.push_back(u);
    dfs(u + 1);
    res.pop_back();

    // 不选
    dfs(u + 1);
}

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

    dfs(1);//枚举到第几个数，选了几个数，状态

    return 0;
}

法二：递归i到n层，选m个停止

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50;

int n, m;
vector<int> res;

void dfs(int u)
{
    // if(u > n + 1) return;
    if(res.size() == m)
    {
        for(int x : res)
            cout << x << " ";
        cout << endl;
        return;
    }

    for(int i = u; i <= n; i ++)
    {
        res.push_back(i);
        dfs(i + 1);
        res.pop_back();
    }
}

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

    dfs(1);//枚举到第几个数，选了几个数，状态

    return 0;
}

法三：递归n层，选m个

#include <iostream>

using namespace std;

const int N = 50;

int n, m;
int way[N];

void dfs(int u, int start)
{
    if(u == m + 1)
    {    
        for(int i = 1; i <= m; i ++)
            cout << way[i] << " ";
        cout << endl;
        return ;
    }

    // 规定了顺序，故不用st
    // st用于避免重复选同一个数， 
    // start用于规定了顺序，用于避免出现重复
    for(int i = start; i <= n; i ++)
    {
        way[u] = i;
        dfs(u + 1, i + 1);
        way[u] = 0;
    }
}

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

    dfs(1, 1);//枚举到第几个数，选了几个数，状态

    return 0;
}

4.22.3—指数型枚举

计算机视觉算法：检测获取一组候选物体，每个物体具有一个特征值，其中 Wi 为正整数，现研究基于特征值选取物问题，表示为< s, c >，s={W1, W2, …, Wn}，表示候选物体的特征值集合，其中 Wi 为正整数，表示第 i 个物品的特征值；C 为正整数，代表需达到目标特征值。要求编程寻找 s 的子集，使子集中物体的特征值之和为 C.

程序输入模式：第一行包括 2 个正整数 N 和 C，N 代表 S 中候选物体总数，C 代表需要达到目标特征值；第二行包括 N 个正整数（1≤N≤100），代表 S。

程序输出格式为：满足条件的 S 的子集（1 行 1 个），或者当问题无解时，输出“None”。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20, M = 3010;

int n, m;
int v[N], st[N];
vector<int> res;
bool flag; //dfs查找时不能用返回值来判断是否找到，因为一定会有失败的查找

void dfs(int u, int sum)
{
    if(u > n + 1 || sum > m) return ;
    if(sum == m)
    {
        for(int x : res) cout << x << " ";
        cout << endl;
        flag = true;
        return ;
    }

    res.push_back(u);
    dfs(u + 1, sum + v[u]);
    res.pop_back();

    dfs(u + 1, sum);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i];
    dfs(1, 0);
    if(!flag) cout << "None";
    return 0;
}